A16534 | 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 组测试数据。

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