# KOITST 24 Palindrome

https://www.acmicpc.net/problem/31572

The KOI (Korea Olympiad in Informatics) organization has created a new event to promote algorithm competitions! To participate in the event, participants must determine whether a secret sequence $S$, known only to KOI, is a palindrome.

A sequence is considered a palindrome when it remains the same even after reversing it. In other words, a sequence $S$ of length $N$ is a palindrome if for all $0 ≤ i ≤ N - 1$, $S[i] = S[N - 1 - i]$. For example, $[1, 2, 3, 2, 1]$, $[1, 2, 2, 1]$ are palindromes, but $[1, 2, 3, 1]$, $[1, 2, 2]$ are not.

You know the length $N$ of the secret sequence $S$ at the beginning. Additionally, you know that $S$ is a sequence of integers ranging from $1$ to $5,000$, inclusive. To assist participants, KOI provides two specially designed machines:

1. The `count_pair` machine requires three different numbers $x$, $y$, and $z$. The machine returns the count of pairs among $S[x]$, $S[y]$, and $S[z]$ that are equal. For example, if $S[x] = S[y] = S[z]$, the machine returns $3$.

2. The `find_character` machine requires an integer $x$ and a list of integers $Y$. The machine returns $1$ if there exists $y ∈ Y$ such that $S[x] = S[y]$, otherwise it returns $0$.

All numbers input to the two machines must be integers ranging from $0$ to $N - 1$, inclusive. The sum of sizes of the input lists for find_character machine must not exceed $N$.

You need to determine whether the secret sequence $S$ is a palindrome using the machines with the minimum number of uses.

# Implementation

You must implement the following function:

`int guess_palindromicity(int N)`

* N: The length of the sequence $S$.
* This function should return $1$ if $S$ is a palindrome, otherwise $0$.
* This function can be called more than once in a single test case, and it can be called multiple times.

The program may call the following functions:

int count_pair(int x, int y, int z)

* $x$, $y$, $z$ must be distinct integers between $0$ and $N - 1$.
* This function returns the count of pairs that are equal among $S[x]$, $S[y]$, and $S[z]$.

int find_character(int x, vector<int> Y)

* $x$ and all elements in $Y$ must be integers between $0$ and $N - 1$.
* This function returns $1$ if there exists $y ∈ Y$ such that $S[x] = S[y]$, otherwise $0$.

In each call to guess_palindromicity, you cannot call count_pair more than $2N$ times and cannot call find_character more than $N$ times.
The sum of the sizes of input lists for find_character must be less than or equal to $N$.

# Constraints

* $5 ≤ N ≤ 5,000$
* $1 ≤ S[i] ≤ 5,000$ for all $0 ≤ i ≤ N - 1$
* The sum of $N$ in each test case is between $5$ and $5,000$.

In this problem, the grader is non-adaptive, meaning $S$ remains fixed at the beginning of the grader's execution and does not change according to queries.

# Subtasks

Scores are awarded as follows for each call to guess_palindromicity. Your score is the minimum of the scores obtained from all calls to guess_palindromicity in all test cases.

Let $A$ be the number of calls to count_pair and $B$ be the number of calls to find_character in each guess_palindromicity call.

If the program fails to terminate correctly or returns an incorrect value in guess_palindromicity, $0$ points are awarded.

The scores awarded when guess_palindromicity returns correctly are as follows:


# Example

Let's say $N = 6$, and $S = [1, 2, 3, 1, 2, 1]$. The grader calls guess_palindromicity(6). An example of function calls is shown below:


Sample Grader

The sample grader receives input in the following format:

Line $1$: $N$
Line $2$: $S[0]$ $S[1]$ $\dots$ $S[N - 1]$

If the program is judged as Accepted, the sample grader outputs Correct : A B, where $A$ is the number of times count_pair was used and $B$ is the number of times find_character was used.

If the program is judged as Wrong Answer, the sample grader outputs Wrong : MSG, where MSG could be one of the following:

* Wrong Input: The input format is incorrect.
* Invalid Query: The values passed to the query are invalid.
* Wrong Guess: When $S$ is a palindrome, but guess_palindromicity returns $0$, or vice versa.

Note that the sample grader may differ from the actual grading grader.