有一款新电子游戏正在发售。在这个游戏世界中，有 $N$ 只怪兽，编号从 $0$ 到 $N - 1$。 每只怪兽都有一个称为“力量值”的整数。怪兽 $i$ ($0 \le i \le N - 1$) 的力量值为 $S_i$。已知怪兽的力量值满足以下条件： 每只怪兽的力量值都是 $0$ 到 $N - 1$ 之间的整数。 没有两只不同的怪兽具有相同的力量值。

你可以选择两只怪兽让它们进行对战。如果怪兽 $a$ 和怪兽 $b$ ($0 \le a \le N - 1, 0 \le b \le N - 1, a \neq b$) 对战，对战结果由以下规则决定： 如果 $|S_a - S_b| = 1$，力量值较小的怪兽获胜。 如果 $|S_a - S_b| > 1$，力量值较大的怪兽获胜。

无论对战结果如何，你可以让同一只怪兽进行任意次数的对战。 你起初不知道怪兽的力量值。你想要知道每只怪兽的力量值。为此，你可以让怪兽进行最多 $25\,000$ 次对战，并获知对战结果。此外，你希望尽量减少对战次数。 请编写一个程序，在给定怪兽数量的情况下，通过让怪兽进行若干次对战来计算出每只怪兽的力量值。

实现细节

你需要提交一个文件。 文件名为 monster.cpp。它应该实现以下函数。程序应使用预处理指令 #include 包含 monster.h。

• std::vector<int> Solve(int N)

对于每个测试用例，该函数会被调用且仅被调用一次。 参数 $N$ 是怪兽的数量。 该函数返回一个描述每只怪兽力量值的数组。在下文中，令 $T$ 为该函数返回的数组。 $T$ 的长度应为 $N$。如果不满足此条件，你的程序将被判为 Wrong Answer [1]。 $T$ 的每个元素都应在 $0$ 到 $N - 1$ 之间（含边界）。如果不满足此条件，你的程序将被判为 Wrong Answer [2]。 * 对于每个 $i$ ($0 \le i \le N - 1$)，应满足 $T[i] = S_i$。如果不满足此条件，你的程序将被判为 Wrong Answer [3]。

你的程序可以调用以下函数：

• bool Query(int a, int b)

使用此函数，你可以让怪兽进行对战。 参数 $a$ 和 $b$ 是将要对战的怪兽的编号。 此函数返回对战结果。如果怪兽 $a$ 获胜，返回 true。如果怪兽 $b$ 获胜，返回 false。 应满足不等式 $0 \le a \le N - 1$ 和 $0 \le b \le N - 1$。如果不满足此条件，你的程序将被判为 Wrong Answer [4]。 应满足条件 $a \neq b$。如果不满足此条件，你的程序将被判为 Wrong Answer [5]。 * 函数 Query 的调用次数不得超过 $25\,000$ 次。如果调用次数超过 $25\,000$ 次，你的程序将被判为 Wrong Answer [6]。

重要提示

• 你的程序可以实现其他内部函数，或使用全局变量。
• 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。

编译与测试

你可以从竞赛网页下载包含示例评测程序的压缩包来测试你的程序。压缩包中还包含你程序的示例源文件。 示例评测程序文件为 grader.cpp。为了测试你的程序，请将 grader.cpp、monster.cpp 和 monster.h 放在同一目录下，并运行以下命令来编译你的程序：

g++ -std=gnu++17 -O2 -o grader grader.cpp monster.cpp

编译成功后，将生成可执行文件 grader。 注意，实际评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它会从标准输入读取数据并将结果写入标准输出。

样例评测程序的输入

示例评测程序从标准输入读取以下数据： $N$ $S_0 \dots S_{N-1}$

样例评测程序的输出

当程序成功终止时，示例评测程序会将以下信息写入标准输出（引号仅为清晰起见）： 如果你的程序被判定为正确，它会写入 Query 函数的调用次数，例如 “Accepted: 100”。 如果你的程序被判定为不正确，它会写入其类型，例如 “Wrong Answer [1]”。

如果你的程序被判定为多种类型的 Wrong Answer，示例评测程序仅报告其中一种。

评测程序说明

对于某些测试用例，实际评测程序是自适应的。这意味着实际评测程序在开始时没有固定的答案，它会根据之前对 Query 函数的调用做出响应。在此保证至少存在一个与所有响应一致的答案。

数据范围

• $4 \le N \le 1\,000$。
• $0 \le S_i \le N - 1$ ($0 \le i \le N - 1$)。
• $S_i \neq S_j$ ($0 \le i < j \le N - 1$)。

子任务

1. (10 分) $N \le 200$。
2. (15 分) 实际评测程序不是自适应的。
3. (75 分) 无附加限制。在此子任务中，如果你的程序正确回答了所有测试用例，你的得分计算如下：
   • 令 $X$ 为该子任务中所有测试用例中 Query 函数调用次数的最大值。
   • 你的得分计算如下：
     • 如果 $10\,000 < X \le 25\,000$，你的得分为 $\lfloor 75 \times \frac{25\,000 - X}{15\,000} \rfloor$ 分。
     • 如果 $X \le 10\,000$，你的得分为 $75$ 分。

样例

输入格式 1

5
3 1 4 2 0

输出格式 1

[3, 1, 4, 2, 0]

说明

样例交互过程如下：