시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 700 | 249 | 175 | 36.842% |
길이가 $N$인 수열 $A$이 있다. 이 수열을 여러 개의 짝수 팰린드롬으로 나누려고 한다.
짝수 팰린드롬은 수열의 길이가 짝수이고 수열을 뒤집어도 뒤집기 전 수열과 동일한 것을 의미한다.
예를 들어, 수열 $[12, 12]$ 은 짝수 팰린드롬이고, 수열 $[12, 21]$은 뒤집으면 $[21, 12]$로 뒤집기 전 수열과 달라서 짝수 팰린드롬이 아니다.
수열을 나누었을 때 모든 부분 수열은 짝수 팰린드롬이어야 한다. 짝수 팰린드롬을 최대한 많이 있도록 나누려고 할 때 짝수 팰린드롬은 최대 몇 개가 있는지 구해보자.
첫 번째 줄에 수열 $A$의 길이가 $N$이 주어진다. $N$은 항상 짝수이다. $(1 \le N \le 5,000)$
다음 줄에는 총 $N$개의 수열 $A$ 원소 $A_{i}$가 주어진다. $(1 \le A_{i} \le 10,000)$
짝수 팰린드롬은 최대 몇 개 있는지 출력한다.
만약 수열을 짝수 팰린드롬을 만족하도록 나눌 수 없는 경우 -1을 출력한다.
10 1 1 5 6 7 7 6 5 5 5
3
(1, 1), (5, 6, 7, 7, 6, 5), (5, 5)
6 1 1 1 1 1 1
3
(1, 1), (1, 1), (1, 1)
6 1 2 3 3 2 2
-1