Tablica jest typu Mountainous (górzysta), jeśli jest ściśle rosnąca, a następnie ściśle malejąca. Zauważ, że tablice typu Mountainous muszą zatem mieć długość co najmniej trzy.

Podtablica (Subarray) jest zdefiniowana jako tablica, którą można uzyskać poprzez usunięcie pewnego prefiksu i sufiksu (być może pustych) z oryginalnej tablicy.

Tablica lub podtablica jest palindromem, jeśli jest tą samą sekwencją czytaną od przodu i od tyłu.

Mając daną tablicę liczb całkowitych, oblicz długość najdłuższej podtablicy, która jest jednocześnie typu Mountainous oraz palindromem.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$), która jest liczbą całkowitą określającą liczbę elementów w tablicy. Każda z kolejnych $n$ linii zawiera pojedynczą liczbę całkowitą $x$ ($1 \le x \le 10^9$). Wartości te tworzą tablicę. Są one podane w kolejności występowania.

Wyjście

Wypisz pojedynczą liczbę całkowitą, która jest długością najdłuższej podtablicy typu Mountainous będącej palindromem, lub $-1$, jeśli taka podtablica nie istnieje.

Przykład

Wejście 1

8
2
1
2
3
2
1
7
8

Wyjście 1

5

Wejście 2

5
2
5
8
7
2

Wyjście 2

-1