CF2173E.Shiro's Mirror Duel

There's no such thing as luck in this world. The victor is decided before the game even starts.

— No Game No Life

This is an interactive problem.

One day, Sora and Shiro feel bored again, so they decide to settle it with a game.

At the beginning, Sora gives Shiro a permutation$^{\text{∗}}$ $p_1,p_2,\ldots,p_n$ of length $n$. In each operation, Shiro may select two distinct indices $x$ and $y$ ($1\le x\ne y\le n$). Then Sora flips a fair coin:

• With probability $0.5$, Sora swaps $p_x$ and $p_y$;
• With probability $0.5$, Sora swaps $p_{n-x+1}$ and $p_{n-y+1}$.

After the operation, Sora replies with the actual pair of indices that were swapped, so that Shiro can update her local permutation accordingly.

Shiro's goal is to sort the permutation $p$ in ascending order by using at most $\lfloor 2.5n+800\rfloor$ operations. Help her!

$^{\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).

在这个世界上，根本不存在运气这种东西。胜负在游戏开始之前便已注定。

——《游戏人生》

这是一道交互式题目。

某天，空与白又感到无聊了，于是决定通过一局游戏来解决争端。

游戏开始时，空会给白一个长度为 $n$ 的排列$^{\text{∗}}$ $p_1,p_2,\ldots,p_n$。在每一次操作中，白可以选择两个不同的下标 $x$ 和 $y$（满足 $1\le x\ne y\le n$）。随后，空会抛掷一枚均匀硬币：

• 以 $0.5$ 的概率，空交换 $p_x$ 与 $p_y$；
• 以 $0.5$ 的概率，空交换 $p_{n-x+1}$ 与 $p_{n-y+1}$。

操作完成后，空会将实际被交换的那对下标告知白，以便白能相应地更新她本地所维护的排列。

白的目标是：至多使用 $\lfloor 2.5n+800\rfloor$ 次操作，将排列 $p$ 升序排序。请帮助她完成这一目标！

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

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

The first line of each test case contains a single integer $n$ ($1\le n\le 4000$) — the length of $p$.

The second line contains $n$ integers $p_1,p_2,\ldots,p_n$ — the elements of $p$.

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

It is guaranteed that there are $50$ tests in this problem.

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

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 4000$）——即序列 $p$ 的长度。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$ —— 即 $p$ 的各个元素。

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

保证本题共有 $50$ 个测试。

In the first test case, $n=5$ and the initial permutation is $[5,1,3,4,2]$.

• We print ? 1 5. The judge replies 1 5, meaning positions $1$ and $5$ are swapped (no mirroring). The array becomes $[2,1,3,4,5]$.
• We print ? 4 5. The judge replies 2 1, which is the mirror of ${4,5}$ because with $n=5$ we have $n-4+1=2$ and $n-5+1=1$. Thus we must swap positions $2$ and $1$. The array becomes $[1,2,3,4,5]$.
• The permutation is now sorted, so we print !. The answer line does not count toward the operation limit.

In the second test case, the given permutation is already increasing, so we just need to output !.

在第一个测试用例中，$n=5$，初始排列为 $[5,1,3,4,2]$。

• 我们输出 ? 1 5。评测机回复 1 5，表示位置 $1$ 和 $5$ 被交换（不进行镜像）。数组变为 $[2,1,3,4,5]$。
• 我们输出 ? 4 5。评测机回复 2 1，这是 ${4,5}$ 的镜像，因为当 $n=5$ 时，有 $n-4+1=2$ 且 $n-5+1=1$。因此我们必须交换位置 $2$ 和 $1$。数组变为 $[1,2,3,4,5]$。
• 此时排列已升序排列，因此我们输出 !。答案行不计入操作次数限制。

在第二个测试用例中，给定的排列本身已是升序排列，因此我们只需输出 !。