这是一个交互问题。
陪审团最初有一个长度为 $$$n$$$ 的序列 $$$a$$$,使得 $$$a_i = i$$$。
陪审团选择了三个整数 $$$i$$$、$$$j$$$、$$$k$$$,使得 $$$1 \leq i < j < k \leq n$$$、$$$j - i > 1$$$。之后,陪审团颠倒了序列 $$$a$$$ 的子段 $$$[i, j - 1]$$$ 和 $$$[j, k]$$$。
反转序列 $$$a$$$ 的子段 $$$[l, r]$$$ 意味着反转序列 i 中元素 $$$a_l, a_{l+1}, \ldots, a_r$$$ 的顺序。 e. $$$a_l$$$ 与 $$$a_r$$$ 交换,$$$a_{l+1}$$$ 与 $$$a_{r-1}$$$ 交换,等等。
你得到了数字$$$n$$$,在提出一些问题后你应该找到$$$i$$$、$$$j$$$、$$$k$$$。
在一个问题中,您可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) 并询问序列 $$$a$$$ 的子段 $$$[l, r]$$$ 上的反转次数。您将得到 $$$(i, j)$$$ 的对数,使得 $$$l \leq i < j \leq r$$$ 且 $$$a_i > a_j$$$。
在最多 $$$40$$$ 问题后找到所选数字 $$$i$$$、$$$j$$$、$$$k$$$。
数字 $$$i$$$、$$$j$$$ 和 $$$k$$$ 在程序开始之前就已确定,并且不取决于您的查询。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的单行包含一个整数 $$$n$$$ ($$$4 \leq n \leq 10^9$$$)。阅读后,您应该通过针对该测试用例提出问题来开始交互过程。给出答案后,您应该:
- 如果这是最后一个测试用例,则终止程序。
- 否则继续下一个测试用例。
互动
要询问子段 $$$[l, r]$$$ 上的反转次数,请打印“? l r”,其中 ($$$1 \leq l \leq r \leq n$$$)。在每个测试用例中您最多可以提出 $$$40$$$ 问题。因此,您应该读取单个整数 $$$x$$$。
- 如果 $$$x = -1$$$,则您的程序提出了无效问题,或者您超出了该测试用例的问题数量。你的程序应该立即终止(否则它可能会得到任何结论而不是“错误答案”)。
- 否则$$$x$$$ 等于序列$$$a$$$ 的子段$$$[l, r]$$$ 上的反转数。
要给出答案,请打印“! i j k”,其中 $$$i$$$、$$$j$$$、$$$k$$$ 是你找到的数字。您应该继续解决下一个测试用例,或者在此之后终止程序。
打印问题或答案后,不要忘记打印行尾并刷新输出。否则,您将得到“超出空闲限制”的判决。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要进行破解,请使用以下格式:
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
接下来的 $$$t$$$ 行包含四个整数 $$$n$$$、$$$i$$$、$$$j$$$、$$$k$$$ ($$$4 \leq n \leq 10^9$$$、$$$1 \leq i < j < k \leq n$$$、$$$j - i > 1$$$)。
示例
输入 #1
2 5 4 3 3 5 2 2 1
输出 #1
? 1 5 ? 2 5 ? 3 5 ! 1 3 5 ? 1 5 ? 2 5 ? 3 5 ! 2 4 5
注意
在第一个测试用例中,$$$i = 1$$$、$$$j = 3$$$、$$$k = 5$$$,因此序列 $$$a$$$ 为 $$$[2, 1, 5, 4, 3]$$$。
在第二个测试用例中,$$$i = 2$$$、$$$j = 4$$$、$$$k = 5$$$,因此序列 $$$a$$$ 为 $$$[1, 3, 2, 5, 4]$$$。