Un arreglo es "montañoso" (Mountainous) si es estrictamente creciente y luego estrictamente decreciente. Tenga en cuenta que, por lo tanto, los arreglos montañosos deben tener una longitud de tres o más.

Un subarreglo (Subarray) se define como un arreglo que puede obtenerse eliminando algún prefijo y sufijo (posiblemente vacíos) del arreglo original.

Un arreglo o subarreglo es un palíndromo (Palindrome) si es la misma secuencia hacia adelante y hacia atrás.

Dado un arreglo de enteros, calcule la longitud del subarreglo más largo que sea tanto montañoso como palíndromo.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^6$), que es el número de enteros en el arreglo.

Cada una de las siguientes $n$ líneas contiene un único entero $x$ ($1 \le x \le 10^9$). Estos valores forman el arreglo. Se proporcionan en orden.

Salida

Imprima un único entero, que es la longitud del subarreglo montañoso palíndromo más largo, o $-1$ si no existe tal arreglo.

Ejemplos

Entrada 1

8
2
1
2
3
2
1
7
8

Salida 1

5

Entrada 2

5
2
5
8
7
2

Salida 2

-1