CF2190C.Comparable Permutations

This is an interactive problem.

For a permutation$^{\text{∗}}$ $g = (g_1, g_2, \ldots, g_m)$, define its reverse as $\operatorname{rev}(g) = (g_m, g_{m-1}, \ldots, g_1)$.

There is a hidden permutation $p$ of size $n$. Your task is to find the lexicographically smallest$^{\text{†}}$ permutation $q$ of size $n$ such that $q \gt p$ and $\operatorname{rev}(q) \gt \operatorname{rev}(p)$.

However, you do not need to output $q$ itself. Instead, you must output a permutation $r$ of size $n$ such that $q_i = p_{r_i}$ for all $1 \le i \le n$. If no such $q$ exists, report that instead.

To find the answer, you can ask at most $3n$ queries of the form $\texttt{? } i \; j$ ($1 \le i, j \le n$). The interactor responds with $1$ if $p_i \lt p_j$ and $0$ otherwise. The interactor is not adaptive, which means that the permutation $p$ is fixed throughout the interaction.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

$^{\text{†}}$ An array $x$ is lexicographically smaller than array $y$ (so $x \lt y$) if and only if one of the following holds:

• $x$ is a prefix of $y$, but $x \ne y$; or
• Let $i$ be the first position where $x_i \neq y_i$ (if it exists), then $x_i \lt y_i$.

这是一个交互式问题。

对于一个排列$^{\text{∗}}$ $g = (g_1, g_2, \ldots, g_m)$，定义其逆序为 $\operatorname{rev}(g) = (g_m, g_{m-1}, \ldots, g_1)$。

存在一个大小为 $n$ 的隐藏排列 $p$。你的任务是找出字典序最小$^{\text{†}}$ 的大小为 $n$ 的排列 $q$，使得 $q \gt p$ 且 $\operatorname{rev}(q) \gt \operatorname{rev}(p)$。

但你无需输出 $q$ 本身。相反，你必须输出一个大小为 $n$ 的排列 $r$，使得对所有 $1 \le i \le n$ 均有 $q_i = p_{r_i}$。若这样的 $q$ 不存在，则应报告该情况。

为求解答案，你可以最多进行 $3n$ 次形如 $\texttt{? } i \; j$（其中 $1 \le i, j \le n$）的查询。交互器将返回 $1$ 表示 $p_i \lt p_j$，否则返回 $0$。交互器是非自适应的，即在整个交互过程中，排列 $p$ 是固定不变的。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

$^{\text{†}}$ 数组 $x$ 字典序小于数组 $y$（即 $x \lt y$）当且仅当满足以下条件之一：

• $x$ 是 $y$ 的前缀，但 $x \ne y$；或
• 设 $i$ 为首个满足 $x_i \neq y_i$ 的位置（若存在），则 $x_i \lt y_i$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^4$) — the size of the hidden permutation $p$.

The hidden permutation $p$ is fixed for the test case and does not change during the interaction. In other words, the interactor is not adaptive.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^4$）——即隐藏排列 $p$ 的长度。

隐藏排列 $p$ 在该测试用例中是固定的，且在交互过程中不会改变。换言之，交互器是非自适应的（non-adaptive）。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^4$。

In the example, the interaction proceeds as follows.

Solution

Jury

Explanation

3

There are $3$ test cases.

5

In the first test case, the hidden permutation is $[5, 4, 2, 3, 1]$, with length $5$. The corresponding permutation $q = [5, 4, 3, 1, 2]$

? 2 1

1

The solution asks whether $p_2 \lt p_1$, and the jury responds with $1$, as $4 \lt 5$.

! 1 2 4 5 3

The solution has miraculously determined the answer and prints $r = [1, 2, 4, 5, 3]$, because, for instance, $q_3 = p_{r_3} = p_4 = 3$ and $q_2 = p_{r_2} = p_2 = 4$.

4

In the second test case, the hidden permutation is $[3, 1, 2, 4]$, with length $4$. The permutation $q$ does not exist for that case.

? 2 3

1

The solution asks whether $p_2 \lt p_3$, and the jury responds with $1$.

? 1 3

0

The solution asks whether $p_1 \lt p_3$, and the jury responds with $0$.

? 1 4

1

The solution asks whether $p_1 \lt p_4$, and the jury responds with $1$.

? 2 2

0

The solution asks whether $p_2 \lt p_2$, and the jury responds with $0$.

! -1

The solution now knows that $p = [3, 1, 2, 4]$ and determines that the corresponding $q$ does not exist, so it prints $-1$.

9

In the third test case, $p = [8, 1, 9, 3, 5, 4, 2, 6, 7]$, with length $n = 9$.

! 1 2 3 6 7 4 5 8 9

The solution decides to guess the answer and outputs $r = [1, 2, 3, 6, 7, 4, 5, 8, 9]$, which turns out to be correct.

Note that the empty lines in the example input and output are for the sake of clarity and do not occur in the real interaction.

在该示例中，交互过程如下所示。

解答

裁判

解释

3

共有 $3$ 个测试用例。

5

第一个测试用例中，隐藏排列为 $[5, 4, 2, 3, 1]$，长度为 $5$。对应的排列 $q = [5, 4, 3, 1, 2]$。

? 2 1

1

解答询问是否满足 $p_2 \lt p_1$，裁判回答 $1$，因为 $4 \lt 5$。

! 1 2 4 5 3

解答奇迹般地确定了答案，并输出 $r = [1, 2, 4, 5, 3]$，例如，$q_3 = p_{r_3} = p_4 = 3$，且 $q_2 = p_{r_2} = p_2 = 4$。

4

第二个测试用例中，隐藏排列为 $[3, 1, 2, 4]$，长度为 $4$。该情况下对应的排列 $q$ 不存在。

? 2 3

1

解答询问是否满足 $p_2 \lt p_3$，裁判回答 $1$。

? 1 3

0

解答询问是否满足 $p_1 \lt p_3$，裁判回答 $0$。

? 1 4

1

解答询问是否满足 $p_1 \lt p_4$，裁判回答 $1$。

? 2 2

0

解答询问是否满足 $p_2 \lt p_2$，裁判回答 $0$。

! -1

解答此时已知 $p = [3, 1, 2, 4]$，并判定对应的 $q$ 不存在，因此输出 $-1$。

9

第三个测试用例中，$p = [8, 1, 9, 3, 5, 4, 2, 6, 7]$，长度 $n = 9$。

! 1 2 3 6 7 4 5 8 9

解答决定直接猜测答案，并输出 $r = [1, 2, 3, 6, 7, 4, 5, 8, 9]$，结果正确。

注意：示例输入与输出中的空行仅为提高可读性，在实际交互中不会出现。