팰린드롬 판별하기

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

수열을 뒤집었을 때의 결과가 원래의 수열과 같아지는 수열을 팰린드롬이라고 한다. 즉, 길이가 $N$인 수열 $S$가 팰린드롬이라는 것은, 모든 $0 ≤ i ≤ 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 ≤ N ≤ 5\\, 000$
• $1 ≤ S\[i] ≤ 5\\, 000$ (모든 $0 ≤ i ≤ N - 1$)
• 한 개의 테스트 케이스에서 주어지는 $N$의 합을 $M$이라 할 때, $5 ≤ M ≤ 5\\, 000$

이 문제에서 그레이더는 적응적이지 않다(NOT adaptive). 이것은 $S$가 그레이더의 수행 초기에 고정되어 쿼리에 따라 변하지 않음을 의미한다.