팰린드롬 판별하기

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$가 팰린드롬인지 판별해야 한다.

팰린드롬 판별하기

문제

제한