这是一个交互问题。
陪审团隐藏了长度为 $$$n$$$ 的排列$$$^\dagger$$$ $$$p$$$。
在一次查询中,您可以通过支付 $$$(r - l)^2$$$ 硬币来选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$)。作为回报,您将获得子数组 $$$[p_l, p_{l + 1}, \ldots p_r]$$$ 中的反转次数$$$^\ddagger$$$。
通过花费最多 $$$5 \cdot n^2$$$ 硬币来查找 $$$p$$$ 中最大元素的索引。
注意:评分器不具有自适应性:在进行任何查询之前排列是固定的。
$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成,顺序任意。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^\ddagger$$$ 数组中的反转数是满足 $$$i < j$$$ 且 $$$a_i > a_j$$$ 的索引对 $$$(i,j)$$$ 的数量。例如,数组 $$$[10,2,6,3]$$$ 包含 $$$4$$$ 反转。反转为$$$(1,2)、(1,3)、(1,4)$$$ 和$$$(3,4)$$$。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) - 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2000$$$) — 隐藏排列 $$$p$$$ 的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
互动
每个测试用例的交互从读取整数 $$$n$$$ 开始。
要进行查询,请输出不带引号的“? l r” ($$$1 \le l < r \le n$$$)。然后,您应该读取一个整数——您的查询的答案。
如果您收到整数 $$$-1$$$ 而不是答案或有效值 $$$n$$$,则意味着您的程序进行了无效查询,超出了查询限制,或者对先前的测试用例给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
当你准备好给出最终答案时,输出不带引号的“! i”($$$1 \le i \le n$$$)——隐藏排列最大值的索引。解决一个测试用例后,您的程序应该立即转移到下一个测试用例。解决所有测试用例后,您的程序应立即终止。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请使用以下格式:
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2000$$$) — 隐藏排列 $$$p$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$),$$$p$$$ 必须是排列。
所有测试用例的 $$$n$$$ 总和不应超过 $$$2000$$$。
示例
输入 #1
2 4 1 0 2 1
输出 #1
? 1 3 ? 3 4 ! 4 ? 1 2 ! 1
注意
在第一个测试中,交互进行如下:
SolutionJuryExplanation2共有$$$2$$$测试用例。4第一个测试用例中,隐藏排列为$$$[1,3,2,4]$$$,长度为$$$4$$$。? 1 3 1解决方案通过支付 $$$4$$$ 硬币来请求子数组 $$$[1,3,2]$$$ 中的反转次数,陪审团以 $$$1$$$ 回应。 3 4 0解决方案通过支付$$$1$$$硬币来请求子数组$$$[2,4]$$$中的反转数,陪审团以$$$0$$$回应。! 4 解决方案以某种方式确定 $$$p_4 = 4$$$,并将其输出。由于输出正确,陪审团继续进行下一个测试用例。2在第二个测试用例中,隐藏排列为$$$[2,1]$$$,长度为$$$2$$$。? 1 2 1解决方案通过支付 $$$1$$$ 硬币来请求子数组 $$$[2,1]$$$ 中的反转数,陪审团以 $$$1$$$ 回应。! 1 解决方案以某种方式确定 $$$p_1 = 2$$$ 并将其输出。由于输出是正确的并且没有更多的测试用例,陪审团和解决方案退出。
请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。