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 > p$ and $\operatorname{rev}(q) > \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 < 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 < 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 < 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$.

For each test case, first read a single integer $n$. You may ask up to $3n$ queries in each test case. To ask a query, print a line in the format $\texttt{?} \; i \; j$ ($1 \le i, j \le n$). As a response to the query, you will get: - $1$ if $p_i < p_j$; - $0$ if $p_i \ge p_j$; - $-1$ if you made an invalid query or if you exceed the limit of $3n$ queries. If your program makes more than $3n$ queries for one test case, or makes an invalid query, then the response to the query will be "-1". After receiving such a response, your program should immediately terminate to receive the verdict **Wrong Answer**. Otherwise, it may receive any other verdict. When you determine the answer for the current test case, print one of the following: - If no valid permutation $q$ exists, print $\texttt{!} \; -1$. - Otherwise, print $\texttt{!} \; r_1 \; r_2 \; \ldots \; r_n$, where $r$ is a permutation of size $n$ and $q_i = p_{r_i}$. Note that this output does not count towards the query limit of $3n$. After that, proceed to the next test case or terminate your program if there are no more test cases. After printing each query do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream. Note that the interactor is **not adaptive**, which means that the hidden permutation is unchanged throughout the interaction. **Hacks** To hack, use the following format. The first line should contain a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The first line of each test case should contain a positive integer $n$ ($2 \le n \le 2 \cdot 10^4$) — the size of $p$. The second line of each test case should contain $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$). You have to guarantee that given $p$ is a permutation and that the sum of $n$ over all test cases does not exceed $2 \cdot 10^4$. $^{\text{∗}}$To flush, use: - fflush(stdout) or cout.flush() in C++; - sys.stdout.flush() in Python; - see the documentation for other languages.

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.