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$ 的单调子序列。关于这个证明的更多信息，你可以参考[维基百科页面](https://en.wikipedia.org/wiki/Erdos-Szekeres%20theorem)。 为此，你最多可以向交互器发起 $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 翻译