팰린드롬 판별하기

KOI사에서는 알고리즘 대회를 홍보하기 위한 새로운 이벤트를 만들었다. 이벤트에 참가하려면 KOI사만이 알고 있는 비밀 수열 $S$가 팰린드롬인지 판별해야 한다.

수열을 뒤집었을 때 원래 수열과 같아지면 그 수열을 팰린드롬이라고 한다. 길이가 $N$인 수열 $S$가 팰린드롬이라는 것은 모든 $0 \le i \le N - 1$에 대해 $S[i] = S[N - 1 - i]$가 성립한다는 뜻이다. 예를 들어 $[1, 2, 3, 2, 1]$과 $[1, 2, 2, 1]$은 팰린드롬이지만, $[1, 2, 3, 1]$과 $[1, 2, 2]$는 팰린드롬이 아니다.

처음에 비밀 수열 $S$의 길이 $N$을 알고 있다. $S$의 각 원소는 1 이상 5,000 이하의 정수이다. 참가자를 돕기 위해 KOI사는 두 가지 기계를 제공한다.

• count_pair 기계에는 서로 다른 세 정수 $x$, $y$, $z$를 입력해야 한다. 기계는 $S[x]$, $S[y]$, $S[z]$ 중 값이 같은 쌍의 개수를 반환한다. 예를 들어 $S[x] = S[y] = S[z]$이면 3을 반환한다.
• find_character 기계에는 정수 $x$와 정수 목록 $Y$를 입력해야 한다. 기계는 $S[x] = S[y]$인 $y$가 $Y$에 있으면 1을, 없으면 0을 반환한다.

두 기계에 입력하는 모든 수는 0 이상 $N - 1$ 이하의 정수여야 한다. find_character 기계에 입력하는 목록 $Y$의 크기의 합은 $N$ 이하여야 한다.

기계를 적은 횟수로 사용해서 비밀 수열 $S$가 팰린드롬인지 판별해야 한다.

• $5 \le N \le 5\,000$
• $1 \le S[i] \le 5\,000$ (모든 $0 \le i \le N - 1$)
• 한 테스트 케이스에서 주어지는 $N$의 합을 $M$이라 하면, $5 \le M \le 5\,000$이다.
• 이 문제의 그레이더는 적응적이지 않다. $S$는 그레이더가 수행을 시작할 때 고정되며, 쿼리에 따라 바뀌지 않는다.