题目背景

本题为交互题。

交互库与 spj 提供者

请不要在代码中加入头文件 monster.h，在 Solve 函数前加上 extern "C"，开头加上 extern "C" bool Query(int,int); 即可。

警告：滥用本题评测将被封号！

题目描述

你圈养了 $N$ 只书虫，这 $N$ 只书虫编号为 $0 \sim N-1$，第 $i$ 只书虫的力量值为 $S_i$，满足 $S_i \in [0,N-1]$，且没有两只书虫的力量值是相等的。

你可以调用最多 $25000$ 次「打架事件」：

• 选择两只编号不相同的书虫 $a,b$：
  • 如果 $|S_a-S_b|=1$，则力量值小的书虫获胜；
  • 如果 $|S_a-S_b|>1$，则力量值大的书虫获胜。

请最小化调用「打架事件」的次数，你可以得到每次「打架事件」的结果，求所有书虫的力量值。

交互格式

你的程序需要实现以下函数：

• std::vector<int> Solve(int N)
  • 对于每组数据，该函数只能被调用一次；
  • $N$：书虫的个数；
  • 该函数返回这 $N$ 只书虫的力量值数组 $T$；
  • 应该满足 $|T|=N$，否则您的程序将会被判为 Wrong Answer [1]；
  • 应该满足 $T_i\in [0,N-1]$，否则您的程序将会被判为 Wrong Answer [2]；
  • 应该满足 $T_i=S_i$，否则您的程序将会被判为 Wrong Answer [3]。

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

• bool Query(int a, int b)
  • 你可以用这个函数调用「打架事件」；
  • $a,b$：书虫 $a$ 与书虫 $b$ 打架；
  • 如果 $a$ 获胜了，则返回 true 否则返回 false；
  • 应该满足 $a \in [0,N-1]\land b \in [0,N-1]$，否则您的程序将会被判为 Wrong Answer [4]；
  • 应该满足 $a \ne b$，否则您的程序将会被判为 Wrong Answer [5]；
  • 调用 Query 函数应该不超过 $25000$ 次。否则您的程序将会被判为 Wrong Answer [6]。

特殊说明

1. 您的程序可以调用其他标准库里的函数，或者使用全局变量；
2. 您的程序不得使用标准输入与标准输出。

输入格式

见「交互格式」。

输出格式

见「交互格式」。

5
3 1 4 2 0

提示

样例 1 解释

样例的交互过程：

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

评测程序示例（样例）

评测程序示例以如下格式读取输⼊数据：

第一行：$N$
第二行：$S_0\ S_1\ \cdots\ S_{N-1}$

评测程序示例以如下格式读取输出数据：

当程序成功结束运行后，样例交互器会在标准输出中输出以下内容：

• 如果你的程序被判为正确，样例交互器会输出类似 Accepted: 100 的信息，其中 $100$ 为你的程序调用 Query 函数的次数；
• 如果你的程序被判为错误，样例交互器的输出内容已在「交互格式」中描述。

如果你的程序有多数错误，样例交互器只会判断其中的一种。

注意，交互器在某些数据中是自适应性的，也就是实际的交互器刚开始并没有一个确定的答案，而是会随着之前 Query 函数的调用逐渐做出响应，能保证至少有一组答案满足交互库做出的响应。

（本来原题有一个工具可以用来检测，但是找不到检测文件了，所以就咕掉了）

数据规模与约定

本题采用捆绑测试。

• Subtask 1（10 pts）：$N \le 200$；
• Subtask 2（15 pts）：实际使用的交互库并不是自适应性的；
• Subtask 3（75 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $4 \le N \le 1000$；
• $0 \le S_i \le N-1$；
• $S_i$ 保证互不相同。

对于 Subtask 3，特有一套评分标准：

如果你的程序通过了所有测试数据，那：

• 设 $X$ 为 Subtask 3 中你的程序对每个测试点调用的 Query 函数的次数的最大值；
• 你的分数将按照下面的过程计算：
  • 如果 $10^4<X \le 2.5 \times 10^4$，你将得到 $\left\lfloor75 \times \dfrac{2.5 \times 10^4-X}{1.5 \times 10^4}\right\rfloor$ 分；
  • 如果 $X \le 10^4$，你将得到 $75$ 分。

说明

翻译自 JOI 2020 / 2021 Open Contest C Monster Game。