题目描述

在一个圆上，有从 $1$ 到 $n$ 的 $n$ 个互不相同的数。沿逆时针方向看，第 $i$ 个顶点上写着数 $p_i$。

对于每一对值 $x$ 和 $y$，从 $x$ 到 $y$ 有两种走法：顺时针或逆时针。在本题中，$n$ 总是奇数，因此这两条路径长度不同。

令 $f(x,y)$ 表示：从数 $x$ 沿较短路径走到数 $y$ 时，途中遇到的数的最小值。

例如，若 $p=[1,5,3,2,7,4,6]$，则值 $5$ 和 $7$ 之间有两条路径，对应顶点值分别为 $[5,3,2,7]$ 和 $[5,1,6,4,7]$。较短路径是第一条，因此

$$f(5,7)=\min\{5,3,2,7\}=2.$$

如果两个排列 $p$ 和 $q$ 对所有 $x,y$ 的函数 $f$ 值都相同，则称它们等价。现在给定一个排列 $p$，你需要通过询问函数 $f(x,y)$，猜出任意一个与它等价的排列 $q$。

提交格式

这是一个非传统题目，使用带 grader 的测试格式。你只需要实现函数 guess，该函数会被评测程序调用，其返回值会作为本题答案。

因此，你提交的代码不得读入或输出任何数据，不得包含 main 函数。必要时可以实现任意数量的辅助函数、结构体、类和全局变量，但整个解答代码必须在一个文件中。

你需要实现如下函数：

std::vector<int> guess(int n);

函数 guess 的参数 $n$ 表示排列长度。

在 guess 的实现中，你可以使用由 grader 实现的函数 min_value。该函数接受两个值 $x$ 和 $y$ 作为参数，并返回 $f(x,y)$。如果进行了非法询问，或询问次数用尽，程序会自动终止。

为了在代码中访问 min_value，你的代码第一行需要包含：

#include "checkpoint.h"

头文件中 min_value 的定义如下：

int min_value(int x, int y);

所有参数，包括值 $x,y$ 以及你返回的排列 $q$，都使用 $1$ 开始编号。

你的函数 guess 必须在调用 min_value 的帮助下，确定未知排列 $p$ 的某个等价排列。也就是说，如果评测方选择了排列 $p$，而 guess 返回了任意与 $p$ 等价的排列 $q$，则答案正确。

在一次 grader 运行中，评测方可能多次调用 guess。此时 min_value 会针对当前这一次 guess 所对应的排列 $p$ 返回对应的 $f(i,j)$。

grader 不是自适应的，也就是说排列 $p$ 会预先固定，不依赖于你的 guess 实现。

本地测试

题目提供了解答模板 checkpoint.cpp，以及头文件 checkpoint.h，其中包含函数 min_value 和 guess 的定义。

为了便于测试，题目提供了 grader 文件 grader.cpp。该文件会从标准输入读取数据，调用函数 guess，并将 guess 的返回值输出到标准输出。在正式评测系统中，grader 文件可能不同。

若要在 C++ 中编译你的 checkpoint.cpp，可以使用如下命令：

g++ -std=c++20 grader.cpp checkpoint.cpp -o grader

执行该命令后，会生成名为 grader 或 grader.exe 的可执行文件，取决于你的操作系统。你可以运行该文件并按指定格式输入测试数据。

如果你在命令行编译时遇到困难，本地测试时可以把 guess 的实现复制进 grader.cpp 并运行 grader.cpp。但提交到评测系统前，你需要只保留 guess 的实现，并记得在代码开头包含头文件。

Grader 输入格式

grader 按如下格式读取测试：

第一行包含整数 $t$（$1 \le t \le 30000$），表示输入数据组数。

每组数据第一行包含一个奇数 $n$（$1 \le n \le 30000$），表示排列长度。

第二行包含 $n$ 个互不相同的数 $p_1,p_2,\ldots,p_n$（$1 \le p_i \le n$），表示评测方选择的排列。

Grader 输出格式

grader 会输出函数 guess 对每组数据猜出的排列。

在 grader.cpp 中有变量 verbose，初值为 $0$。增大该值后，grader 会给出关于你的解答和询问的更详细信息。

样例

样例输入

2
3
1 2 3
5
1 4 2 3 5

样例输出

queries count => 3
queries count => 10

计分方式

测试数据包含四个测试组。前三个测试组只有当该组所有测试点以及要求的若干前置组全部通过时，才能获得分数。最后一个测试组的分数等于该组中每个测试点所得分数的最小值。

对每个测试点，令 $N$ 为所有输入数据组中 $n$ 的总和，$Q$ 为所有输入数据组中调用 min_value 的总次数上限。

组别	分数	$N$	$Q$	前置组	备注
0		-	$Q=4950$	-	样例
1	10	$N \le 100$			$p_{2i-1}=\frac{n-1}{2}+i$，其中 $1\le i\le \frac{n+1}{2}$
2	20			0,1	-
3		$N \le 1000$	$Q=100000$	0,1,2
4	60	$N \le 30000$	$Q=1000000$	-	按询问次数计分

最后一组按公式计分。若你在某个测试中进行了 $x$ 次询问，则分数为：

$$\mathrm{score}=\min\left(60,\left\lfloor 95\cdot\left(1-\frac{x}{10^6}\right)\right\rfloor\right).$$

该组最终分数为第四组所有测试点所得分数的最小值。