这是一道交互题。

题目描述

你迷上了一个解谜游戏。在游戏的这一关中，你的任务是打开一个宝箱。

你手中有 $n$ 把钥匙，编号为 $0\sim n-1$；宝箱上有 $n$ 个凹槽，编号也为 $0\sim n-1$。你的任务是收集相关线索，将钥匙按特定的顺序顺序插入凹槽，然后按动开关打开宝箱。这个正确的钥匙顺序可以视为一个长度为 $n$ 的排列 $p$（下标从 $0$ 开始）代表 $i$ 号凹槽中应当放入 $p_i$ 号钥匙。

你的尝试可以视为给出一个长度为 $n$ 的排列 $q$，表示在 $i$ 号凹槽中放入 $q_i$ 号钥匙。如果对于每个 $0 \le i \le n-1$ 均有 $p_i=q_i$，则说明你的尝试是正确的，你将打开宝箱并顺利通关，否则通关失败。你只有一次尝试机会，因此你务必格外谨慎。

经过仔细地观察，你发现了这个宝箱的奥秘所在：宝箱的后面有一个隐藏的按钮。当你给出一个排列 $q$ 并相应地将钥匙放入凹槽之后，你可以按动隐藏按钮，宝箱将给出有多少把钥匙放置的位置是正确的——即有多少个 $0 \le i \le n-1$ 满足 $p_i=q_i$。将你的这一操作称为一次询问，你可以在按下最终的开箱开关之前，多次改变你的排列 $q$ 并进行询问，直到你收集到足够的信息能确定答案排列 $p$ 为止。

但出于游戏难度和趣味性的考虑，还有一条特殊规定：你向宝箱询问的次数不得超过 $20000$ 次，一旦超过，宝箱将立刻永久上锁，也就意味着你的游戏失败。能不能取得游戏的成功，就看你的本事了！

实现细节

你不需要，也不应该实现主函数。你需要在程序开头添加 #include "puzzle.h" 并实现如下函数：

void play(int n);

• 其中，$n$ 表示排列长度。
• 交互库运行过程中，该函数将会被调用恰好一次。

你可以调用以下两个函数：

int query(const std::vector<int> &q);

• 其中， $q$ 应当是一个长度为 $n$ 的排列，即 $q$ 的长度应当为 $n$ ，且 $0\sim n-1$ 中的所有整数在 $q_{0} \sim q_{n-1}$ 中均恰好出现一次。

• 函数将比较你给出的排列 $q$ 与答案排列 $p$，并返回本次询问的结果，即有多少个整数 $i$ 满足 $0 \leq i \leq n-1$ 且 $p_i = q_i$。

• 你调用该函数的次数不应当超过 $20000$。

void check(const std::vector<int> &q);

• 其中， $q$ 应当是一个长度为 $n$ 的排列，即 $q$ 的大小应当为 $n$ ，且 $0\sim n-1$ 中的所有整数在 $q_{0} \sim q_{n-1}$ 中均恰好出现一次。
• 这个函数应当在你的程序运行 play 函数时恰好被执行一次。
• 函数将比较你给出的排列 $q$ 与答案排列 $p$，如果 $p=q$ 则认为你给出的答案正确，否则认为你给出的答案错误。
• 无论如何，交互库将在执行完该函数后，输出相应信息并立即终止运行。

你应当保证调用 query 或 check 函数时传入的参数符合上述要求。

你可以查看下发文件中的参考交互库了解更多实现细节。

测试程序方式

下发文件中提供了交互库的参考实现 grader.cpp。最终测试时所用的交互库实现与该实现有不同，因此选手的解法不应依赖交互库实现。

假设你的源程序名为 puzzle.cpp，你需要将下发文件放入源程序所在的目录中，并在目录下使用如下命令编译得到可执行程序：

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -lm

运行按上述方法编译得到的可执行文件时：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行：一个正整数 $n$，表示排列长度。你需要保证 $2 \leq n \leq 1000$；
  • 第二行： $n$ 个整数 $p_0,p_1,\cdots,p_{n-1}$，表示答案排列。你需要保证 $p_0,\cdots,p_{n-1}$ 是一个长度为 $n$ 的排列，即 $0 \sim n-1$ 中的所有整数均恰好出现一次。

• 读入完成之后，交互库将用该组数据进行测试，并输出如下内容：

  • 如果你的程序正常运行，调用 query 函数的次数不超过 $20000$，并在调用 check 函数时传入了正确的排列，则会输出以下内容：

    Correct.
    cnt = x

    其中 $x$ 为你的程序调用 query 函数的次数。

  • 否则，将会输出相应的错误信息。

样例

输入

3
1 0 2

输出

Correct.
cnt = 3

解释

这是使用下发的 grader.cpp 和能够正确运行的源程序得到的可能输出文件。

对于此样例，一种可能的调用方式为：

• 调用 query([0, 1, 2])，返回 $1$；
• 调用 query([0, 2, 1])，返回 $0$；
• 调用 query([1, 0, 2])，返回 $3$；
• 调用 check([1, 0, 2])。

评分方式

评测时，你只需在 OJ 上提交你的源程序，修改下发的其他文件不会对评测结果产生影响。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件以外，在一个测试点中，若你的程序执行了非法的函数调用、没有调用 check 函数或 check 函数给出了错误回答、或调用 query 函数的次数超过 $20000$，该测试点将会获得 $0$ 分。否则，该测试点的得分将由下述“子任务”中的描述给出。

子任务

本题使用捆绑测试。对于每个子任务而言，你的得分是子任务中所有测试点得分的最小值。

对于所有测试点，$1 \leq n \leq 1000$。

​

对于前 $6$ 个子任务，如果你的程序正常运行，调用 query 函数的次数不超过 $20000$，并在调用 check 函数时传入了正确的排列，则可以获得该测试点的满分。

对于第 $7$ 个子任务，你的程序在上述基础之上还可能获得部分分。设你的程序调用 query 的次数为 $m$，则你的得分如下：

​

注意事项

保证对于任何合法的数据及在限制范围内的调用，交互库本身运行所用的时间不会超过 $\mathrm{0.2s}$，运行所用的空间不会超过 $\mathrm{128MiB}$。

交互库正常运行需包含的头文件已经在下发的参考交互库中给出，你的程序可以包含你需要的头文件。

本题的交互库不是自适应的，即在 play 函数调用之前答案排列就已经确定，不会根据你的询问而变化。

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。