KOI 公司为了宣传算法竞赛，举办了一项新活动！为了参加活动，你需要判断 KOI 公司所掌握的秘密序列 $S$ 是否为回文序列。
如果一个序列反转后的结果与原序列相同，则称该序列为回文序列。也就是说，对于长度为 $N$ 的序列 $S$，它是回文序列等价于对于所有 $0 \le i \le 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$。如果存在 $y \in Y$ 使得 $S[x] = S[y]$，则该机器返回 $1$，否则返回 $0$。- 输入到两种机器中的所有数必须是 $0$ 以上 $N - 1$ 以下的整数。
- 输入到
find_character机器中的 $Y$ 的大小之和必须不超过 $N$。
你需要通过尽可能少地使用机器来判断秘密序列 $S$ 是否为回文序列。
实现细节
你需要实现以下函数：
int guess_palindromicity(int N)- $N$：序列 $S$ 的长度。
- 该函数若 $S$ 为回文序列则应返回 $1$，否则返回 $0$。
- 该函数在单个测试用例中会被调用 $1$ 次或多次，也可能被多次调用。
程序可以调用以下函数：
int count_pair(int x, int y, int z)- $x, y, z$ 必须是 $0$ 以上 $N - 1$ 以下的互不相同的整数。
- 该函数返回 $S[x], S[y], S[z]$ 中相同元素的对数。
- 在每次
guess_palindromicity调用中，该函数调用次数不能超过 $2N$ 次。
int find_character(int x, vector<int> Y)- $x$ 以及 $Y$ 中的所有元素必须是 $0$ 以上 $N - 1$ 以下的整数。
- 若存在 $y \in Y$ 使得 $S[x] = S[y]$，则该函数返回 $1$，否则返回 $0$。
- 在每次
guess_palindromicity调用中，该函数调用次数不能超过 $N$ 次。 - 在每次
guess_palindromicity调用中，该函数调用时 $Y$ 的大小之和必须不超过 $N$。
提交的源代码中不得执行任何输入输出函数。
数据范围
- $5 \le N \le 5\,000$
- $1 \le S[i] \le 5\,000$ (对于所有 $0 \le i \le N - 1$)
- 单个测试用例中 $N$ 的总和为 $M$，满足 $5 \le M \le 5\,000$
本题中的评测器不是自适应的（NOT adaptive）。这意味着 $S$ 在评测器运行初期就已经固定，不会根据查询而改变。
子任务
每次 guess_palindromicity 调用都会按如下方式计分。你的提交所获得的分数是所有测试用例中 guess_palindromicity 调用所获分数的最小值。
在每次 guess_palindromicity 调用中，设 count_pair 函数的调用次数为 $A$，find_character 函数的调用次数为 $B$。
如果程序未能正常结束，或者 guess_palindromicity 返回的值错误，则得 $0$ 分。当 guess_palindromicity 返回值正确时，得分如下表所示：
| 条件 | 得分 |
|---|---|
| $A \le 2N, 2 \le B \le N$ | $15$ |
| $N < A \le 2N, B \le 1$ | $50$ |
| $\lfloor \frac{N}{2} \rfloor + 2 < A \le N, B \le 1$ | $70$ |
| $A = \lfloor \frac{N}{2} \rfloor + 2, B \le 1$ | $90$ |
| $A \le \lfloor \frac{N}{2} \rfloor + 1, B \le 1$ | $100$ |
样例
设 $N = 6, S = [1, 2, 3, 1, 2, 1]$。评测器调用 guess_palindromicity(6)。函数调用的示例如下：
| 调用 | 返回值 |
|---|---|
count_pair(0, 1, 2) |
$0$ |
count_pair(3, 4, 5) |
$1$ |
count_pair(0, 3, 5) |
$3$ |
find_character(2, {0, 1, 3, 4, 5}) |
$0$ |
find_character(1, {0, 2, 4}) |
$1$ |
Sample grader
Sample grader 按以下格式接收输入：
- Line 1: $N$
- Line 2: $S[0] \ S[1] \ \dots \ S[N - 1]$
如果程序被判定为 Accepted，Sample grader 将输出 Correct : A B。其中 $A$ 是使用 count_pair 的次数，$B$ 是使用 find_character 的次数。
如果程序被判定为 Wrong Answer，Sample grader 将输出 Wrong : MSG。其中 MSG 为以下之一：
Wrong Input：输入格式错误。Invalid Query：查询中包含非法值。Wrong Guess：$S$ 是回文序列但guess_palindromicity返回了 $0$，或者反之。
请注意，Sample grader 可能与实际评测时使用的评测器不同。