CF2152E.Monotone Subsequence

这是一个交互题。

Faker 又在调皮了。你让他出一道好玩的查询题，结果他却出了一道需要你来和他互动的题。Faker 把一个排列藏了起来，而你需要通过与他的互动来推断出一些有趣的信息。

给定一个整数 $n$。Faker 藏了一个长度为 $n^2+1$ 的排列 $p_1, p_2, \ldots, p_{n^2+1}$。你的目标是找出这个隐藏排列中长度恰好为 $n+1$ 的单调子序列（递增或递减皆可）。可以证明，任意长度为 $n^2+1$ 的排列都必然包含一个长度为 $n+1$ 的单调子序列。关于这个证明的更多信息，你可以参考维基百科页面。

为此，你最多可以向交互器发起 $n$ 次“摩天大楼”查询，查询方式如下：

• 你提供一个长度为 $k$ 的下标集合，按严格递增顺序排列：$i_1, i_2, \ldots, i_k$。
• 交互器会查看排列中这些下标对应的数值：$p_{i_1}, p_{i_2}, \ldots, p_{i_k}$。
• 之后，交互器返回其中可见的摩天大楼的下标。下标 $i_j$ 可见，当且仅当 $p_{i_j}$ 的值大于你查询中该下标前的所有元素的值。也就是说，$p_{i_j} > p_{i_m}$，对于所有 $1 \le m < j$。这等价于找出序列 $(p_{i_1}, \ldots, p_{i_k})$ 的左侧最大值的位置。

在最多 $n$ 次查询后，你需要给出一个长度恰好为 $n+1$ 的有效单调子序列。

注意，排列 $p$ 在你查询前就已经确定，不会根据查询而改变。

$^*$排列定义为长度为 $m$ 的数组，包含 $1$ 到 $m$ 的所有整数且各不重复，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（长度为 $3$ 却有 $4$）。

每个测试点包含多组测试数据。第一行为测试用例组数 $t$（$1 \le t \le 5000$）。接下来每组测试数据一行，包含一个整数 $n$（$1 \le n \le 100$）。

保证所有测试用例中 $\sum (n^2+1) \le 10\,001$。

（与交互器详见题目说明）

对于第一个测试用例，$n=1$，隐藏排列为 $p=[1,2]$。

• 对于查询 ? 2 1 2，可见的摩天大楼在下标 $1$ 和 $2$，交互器返回 2 1 2。
• 在下标 $1,2$ 处报告一个长度为 $2$ 的递增子序列。

对于第二个测试用例，$n=2$，隐藏排列为 $p=[5,3,4,1,2]$。

• 对于查询 ? 3 1 2 3，可见的摩天大楼在下标 $1$，交互器返回 1 1。
• 对于查询 ? 3 2 3 5，可见的摩天大楼在下标 $2$ 和 $3$，交互器返回 2 2 3。
• 在下标 $1,3,4$ 处报告一个长度为 $3$ 的递减子序列。

虽然 Faker 扮演的是交互器，但交互器永远不会欺骗你。

由 ChatGPT 5 翻译