Palindrome Check

KOI is running a new event to promote its algorithm contest. To take part, you must determine whether a secret sequence $S$, known only to KOI, is a palindrome.

A sequence is a palindrome if it stays the same when reversed. A sequence $S$ of length $N$ is a palindrome if $S[i] = S[N - 1 - i]$ holds for every $0 \le i \le N - 1$. For example, $[1, 2, 3, 2, 1]$ and $[1, 2, 2, 1]$ are palindromes, but $[1, 2, 3, 1]$ and $[1, 2, 2]$ are not.

You initially know the length $N$ of the secret sequence $S$. Each element of $S$ is an integer from 1 to 5,000. To help the participants, KOI provides two machines.

• The count_pair machine takes three distinct integers $x$, $y$, and $z$. It returns the number of equal pairs among $S[x]$, $S[y]$, and $S[z]$. For example, if $S[x] = S[y] = S[z]$, it returns 3.
• The find_character machine takes an integer $x$ and a list of integers $Y$. It returns 1 if some $y$ in $Y$ satisfies $S[x] = S[y]$, and 0 otherwise.

Every number you input to either machine must be an integer from 0 to $N - 1$. The sum of the sizes of the lists $Y$ you input to find_character must be at most $N$.

You must determine whether $S$ is a palindrome while using the machines a small number of times.

• $5 \le N \le 5\,000$
• $1 \le S[i] \le 5\,000$ (for every $0 \le i \le N - 1$)
• Let $M$ be the sum of $N$ over all test cases in one input. Then $5 \le M \le 5\,000$.
• The grader is not adaptive. $S$ is fixed when the grader starts and does not change with the queries.