Un tableau est dit « montagneux » (Mountainous) s'il est strictement croissant, puis strictement décroissant. Notez que les tableaux montagneux doivent donc avoir une longueur d'au moins trois.

Un sous-tableau (Subarray) est défini comme un tableau pouvant être obtenu en supprimant un préfixe et un suffixe (éventuellement vides) du tableau original.

Un tableau ou un sous-tableau est un palindrome s'il s'agit de la même séquence dans les deux sens.

Étant donné un tableau d'entiers, calculez la longueur du plus long sous-tableau qui est à la fois montagneux et palindrome.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^6$), qui est le nombre d'entiers dans le tableau.

Chacune des $n$ lignes suivantes contient un entier unique $x$ ($1 \le x \le 10^9$). Ces valeurs forment le tableau. Elles sont données dans l'ordre.

Sortie

Affichez un seul entier, qui est la longueur du plus long sous-tableau montagneux et palindrome, ou $-1$ si aucun sous-tableau de ce type n'existe.

Exemples

Entrée 1

8
2
1
2
3
2
1
7
8

Sortie 1

5

Entrée 2

5
2
5
8
7
2

Sortie 2

-1