길이가 $N$인 수열 $A$이 있다. 이 수열을 여러 개의 짝수 팰린드롬으로 나누려고 한다.</p>

짝수 팰린드롬은 수열의 길이가 짝수이고 수열을 뒤집어도 뒤집기 전 수열과 동일한 것을 의미한다.

예를 들어, 수열 $[12, 12]$ 은 짝수 팰린드롬이고, 수열 $[12, 21]$은 뒤집으면 $[21, 12]$로 뒤집기 전 수열과 달라서 짝수 팰린드롬이 아니다.

수열을 나누었을 때 모든 부분 수열은 짝수 팰린드롬이어야 한다. 짝수 팰린드롬을 최대한 많이 있도록 나누려고 할 때 짝수 팰린드롬은 최대 몇 개가 있는지 구해보자.

입력 형식

첫 번째 줄에 수열 $A$의 길이가 $N$이 주어진다. $N$은 항상 짝수이다. $(1 \le N \le 5,000)$</p>

다음 줄에는 총 $N$개의 수열 $A$ 원소 $A_{i}$가 주어진다. $(1 \le A_{i} \le 10,000)$

출력 형식

짝수 팰린드롬은 최대 몇 개 있는지 출력한다.</p>

만약 수열을 짝수 팰린드롬을 만족하도록 나눌 수 없는 경우 -1을 출력한다.

예제 입력 1

10
1 1 5 6 7 7 6 5 5 5

예제 출력 1

3

예제 입력 2

6
1 1 1 1 1 1

예제 출력 2

3

예제 입력 3

6
1 2 3 3 2 2

예제 출력 3

-1