题目描述

译自 JOI Open 2021 T3 「モンスターゲーム / Monster Game」。

一款新游戏正在发售。在这个游戏的世界中，有 $N$ 个怪兽，编号为 $0$ 到 $N-1$。每个怪兽都有一个整数的力量值。第 $i$ $(0 \le i \le N-1)$ 个怪兽的力量值为 $S_i$。力量值满足以下条件：

• 每个怪兽的力量值是 $0$ 到 $N-1$ 之间的一个整数（包含端点）。
• 没有任何两个不同的怪兽拥有相同的力量值。

你可以选择两个怪兽让他们打架。如果怪兽 $a$ 和怪兽 $b$ 打架（$0 \le a, b \le N-1$，$a \ne b$），结果按如下方式确定：

• 如果 $|S_a - S_b| = 1$，则力量值较小的怪兽获胜。
• 如果 $|S_a - S_b| > 1$，则力量值较大的怪兽获胜。

忽略打架的结果，你可以让相同的怪兽打任意多次架。

一开始，你不知道怪兽的力量值。你想要知道每个怪兽的力量值。为了达到这个目的，你可以让怪兽之间打至多 $25\,000$ 次架，并且你会知道每次打架的结果。此外，你想最小化打架的次数。

给出怪兽的数量，写一个程序通过让怪兽打架计算每个怪兽的力量值。

---

实现细节

你需要在程序中包含 monster.h 头文件。程序需要实现以下函数：

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

对于每组数据，这个函数恰好被调用一次。

• 参数 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$ 和 $b$。
• 这个函数会返回打架的结果。如果怪兽 $a$ 赢了，则返回 true，否则返回 false。
• 必须满足 $0 \le a \le N-1$ 和 $0 \le b \le N-1$。如果条件不满足，你的程序会被判为 Wrong Answer [4]。
• 必须满足 $a \ne b$。如果条件不满足，你的程序会被判为 Wrong Answer [5]。
• 函数 Query 不能调用超过 $25\,000$ 次。如果条件不满足，你的程序会被判为 Wrong Answer [6]。

---

交互器输入

第一行一个整数 $N$。

第二行 $N$ 个整数 $S_0, S_1, \ldots, S_{N-1}$。

---

交互器输出

当程序成功停止时，样例交互器会向标准输出输出以下信息：

• 如果你的程序被判为正确，交互器会输出形如 Accept: 100 的信息，其中 $100$ 是 Query 函数调用的次数。
• 如果你的程序被判为错误，交互器会输出形如 Wrong Answer [1] 的信息。

如果程序中有多种错误之处，样例交互器只会报告其中的一种。

---

交互器注意事项
对于一些测试点，实际采用的评分器是适应性的。也就是说，实际的评分器一开始并没有一个确定的答案，它会根据 Query 之前的调用来做出响应。此处保证至少有一组答案符合所有的响应。

---

提交注意事项
提交本题时，应当使用 GNU C++ 17 标准，否则会出现编译错误。

---

样例交互

样例输入：

5
3 1 4 2 0

样例交互过程：

函数调用	返回值	函数调用	返回值
Solve(5)
Query(1, 0)	false
Query(4, 0)
Query(1, 3)	true
返回 [3, 1, 4, 2, 0]

---

数据范围与提示

对于全部数据，满足：

• $4 \le N \le 10^3$
• $0 \le S_i \le N-1$ $(0 \le i \le N-1)$
• $S_i \ne S_j$ $(0 \le i < j \le N-1)$

详细子任务附加限制及分值如下表所示：

子任务	附加限制	分值
1	$N \le 200$	10
2	实际使用的评分器不是适应性的	15
3	无附加限制	75

对于子任务 3，如果你的程序正确通过了所有测试数据，你的得分按如下方式计算：

令 $X$ 为在这个子任务中所有测试点调用 Query 函数次数的最大值。

• 如果 $10\,000 < X \le 25\,000$，你的得分为 $\left\lfloor 75 \times \frac{25\,000 - X}{15\,000} \right\rfloor$ 分。
• 如果 $X \le 10\,000$，你的得分为 $75$ 分。