这是一个交互问题。
有一天,Sora和Shiro再次感到无聊,所以他们决定用游戏来解决这个问题。
一开始,Sora给Shiro一个排列$$$^{\text{*}}$$$ $$$p_1,p_2,\ldots,p_n$$$,长度为$$$n$$$。在每个操作中,Shiro 可以选择两个不同的索引 $$$x$$$ 和 $$$y$$$ ($$$1\le x\ne y\le n$$$)。然后索拉抛了一枚公平的硬币:
- Sora 以 $$$0.5$$$ 的概率交换 $$$p_x$$$ 和 $$$p_y$$$;
- Sora 以 $$$0.5$$$ 的概率交换 $$$p_{n-x+1}$$$ 和 $$$p_{n-y+1}$$$。
操作完成后,Sora 回复实际交换的一对索引,以便 Shiro 可以相应地更新她的本地排列。
Shiro 的目标是通过最多使用 $$$\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$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 测试。
互动
对于每个测试用例,您最多可以使用 $$$\lfloor 2.5n+800\rfloor$$$ 移动来按升序对排列 $$$p$$$ 进行排序。
要进行移动,您应该按以下格式打印新行:
- $$$\mathtt{?}\; x\; y$$$ ($$$1 \le x \ne y \le n$$$) — Shiro 在这一步中选择的两个索引。
作为对此举的回应,您将收到两个整数 $$$u$$$ 和 $$$v$$$ — Sora 交换的实际索引对。保证 $$$(u, v)$$$ 是从 $$$(x, y)$$$ 和 $$$(n-x+1, n-y+1)$$$ 中等概率随机选择的。
要报告排列已按升序排序,您应该打印一个包含单个字符 $$$\mathtt{!}$$$ 的新行。这确实 不 算作 $$$\lfloor 2.5n+800\rfloor$$$ 移动之一。
之后,继续进行下一个测试用例,或者如果是最后一个测试用例则终止程序。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
在此问题中,黑客被禁用。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 5 5 1 3 4 2 1 5 2 1 2 1 2
输出复制
? 1 5 ? 4 5 ! !
注意
在第一个测试用例中,$$$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]$$$。
- 排列现已排序,因此我们打印 !。答案行不计入操作限制。
在第二个测试用例中,给定的排列已经在增加,所以我们只需要输出 !.