CFCF2173E.Shiro's Mirror Duel

这个世界上没有所谓的幸运。胜者在游戏开始前就已经决定了。

——《NO GAME NO LIFE》

这是一个交互题。

有一天，空与白又感到无聊，于是他们决定用一场游戏来解决。

一开始，空给白一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$。每进行一次操作，白可以选择两个不同的下标 $x$ 和 $y$（$1 \leq x \neq y \leq n$）。然后空会抛一枚公正的硬币：

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

操作后，空会回复实际被交换的下标对，使白可以相应地更新自己的排列。

白的目标是在不超过 $\lfloor 2.5n+800\rfloor$ 次操作内，将排列 $p$ 升序排序。请你帮助她达成目标！

$^{\ast}$ 长度为 $n$ 的排列是指包含 $n$ 个从 $1$ 到 $n$ 的不同整数的数组。例如，$[2,3,1,5,4]$ 是一个排列，$[1,2,2]$ 不是（因为 $2$ 出现了两次），$[1,3,4]$ 也不是（因为 $n=3$ 但出现了 $4$）。

每个测试包含多组数据。第一行包含测试数据组数 $t$（$1 \leq t \leq 100$）。每组测试数据描述如下：

每组测试的第一行包含一个整数 $n$（$1 \leq n \leq 4000$），表示排列 $p$ 的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，表示排列 $p$ 的元素。

保证所有测试数据中 $\sum n \leq 2\cdot 10^4$。

保证本题共有 50 组测试数据。

（交互题，具体细节请参考题面或平台说明。）

在第一个测试用例中，$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]$。
• 现在排列已经有序，所以我们输出 !。这行输出不计入操作次数限制。

在第二个测试用例中，给定的排列本身就是升序排列，仅需输出 !。