KOI has created a new event to promote algorithm competitions! To participate in the event, you must determine whether a secret sequence $S$, known only to KOI, is a palindrome.

A sequence is called a palindrome if it is the same when reversed. That is, a sequence $S$ of length $N$ is a palindrome if $S[i] = S[N - 1 - i]$ for all $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 are initially given the length $N$ of the secret sequence $S$. You also know that $S$ consists of integers between $1$ and $5\,000$, inclusive. To assist event participants, KOI provides two specially designed machines:

• The count_pair machine requires three distinct integers $x, y, z$ as input. The machine returns the number of identical pairs among $S[x], S[y], S[z]$. For example, if $S[x] = S[y] = S[z]$, the machine returns $3$.
• The find_character machine requires an integer $x$ and a list of integers $Y$ as input. The machine returns $1$ if there exists $y \in Y$ such that $S[x] = S[y]$, and $0$ otherwise.
• All numbers input to both machines must be integers between $0$ and $N - 1$, inclusive.
• The sum of the sizes of $Y$ input to the find_character machine must be at most $N$.

You must determine whether the secret sequence $S$ is a palindrome by using the machines a limited number of times.

Implementation Details

You must implement the following function:

int guess_palindromicity(int N)

• $N$: The length of the sequence $S$.
• This function must return $1$ if $S$ is a palindrome, and $0$ otherwise.
• This function is called at least once per test case and may be called multiple times.

Your program can 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$, inclusive.
• This function returns the number of identical pairs among $S[x], S[y], S[z]$.
• In each call to guess_palindromicity, this function can be called at most $2N$ times.

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

• $x$ and all elements of $Y$ must be integers between $0$ and $N - 1$, inclusive.
• This function returns $1$ if there exists $y \in Y$ such that $S[x] = S[y]$, and $0$ otherwise.
• In each call to guess_palindromicity, this function can be called at most $N$ times.
• In each call to guess_palindromicity, the sum of the sizes of $Y$ for all calls to this function must be at most $N$.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $5 \le N \le 5\,000$
• $1 \le S[i] \le 5\,000$ (for all $0 \le i \le N - 1$)
• Let $M$ be the sum of $N$ given in a single test case, then $5 \le M \le 5\,000$

In this problem, the grader is NOT adaptive. This means $S$ is fixed at the beginning of the grader's execution and does not change based on your queries.

Subtasks

For each call to guess_palindromicity, points are awarded in the following manner. The score your submission receives is the minimum of the scores obtained from all guess_palindromicity calls across all test cases.

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

If the program does not terminate normally or the value returned by guess_palindromicity is incorrect, $0$ points are awarded. The points awarded when the value returned by guess_palindromicity is correct are shown in the table below.

Examples

Example 1

Let $N = 6, S = [1, 2, 3, 1, 2, 1]$. The grader calls guess_palindromicity(6).

Input 1

6
1 2 3 1 2 1

Output 1

Correct : 3 2

Note

The example above shows a possible sequence of calls: count_pair(0, 1, 2) returns $0$. count_pair(3, 4, 5) returns $1$. count_pair(0, 3, 5) returns $3$. find_character(2, {0, 1, 3, 4, 5}) returns $0$. find_character(1, {0, 2, 4}) returns $1$.

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. Here, $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. Here, $MSG$ is one of the following:

• Wrong Input: The input format is incorrect.
• Invalid Query: The value provided in the query is invalid.
• Wrong Guess: $S$ is a palindrome but guess_palindromicity returned $0$, or vice versa.

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