배열이 엄격하게 증가하다가 엄격하게 감소하는 경우 이를 산 모양(Mountainous) 배열이라고 한다. 산 모양 배열은 길이가 3 이상이어야 함에 유의하라.

부분 배열(Subarray)은 원래 배열에서 접두사와 접미사(비어 있을 수도 있음)를 제거하여 얻을 수 있는 배열로 정의된다.

배열이나 부분 배열이 앞에서부터 읽을 때와 뒤에서부터 읽을 때 동일한 수열인 경우 이를 팰린드롬(Palindrome)이라고 한다.

정수 배열이 주어졌을 때, 산 모양이면서 동시에 팰린드롬인 가장 긴 부분 배열의 길이를 구하라.

입력

첫 번째 줄에는 배열의 정수 개수인 $n$ ($1 \le n \le 10^6$)이 주어진다. 다음 $n$개의 줄에는 각각 하나의 정수 $x$ ($1 \le x \le 10^9$)가 주어진다. 이 값들은 순서대로 배열을 구성한다.

출력

산 모양이면서 팰린드롬인 가장 긴 부분 배열의 길이를 출력하라. 만약 그러한 배열이 존재하지 않으면 -1을 출력하라.

예제

입력 1

8
2
1
2
3
2
1
7
8

출력 1

5

입력 2

5
2
5
8
7
2

출력 2

-1