简单版和困难版之间的唯一区别是查询数量的限制。
这是一个交互问题。
存在一个由 $$$n$$$ 不同数字组成的数组 $$$a$$$。在一个查询中,您可以询问子段 $$$a[l..r]$$$ 中第二个最大元素的位置。在不超过 20 次查询中找到数组中最大元素的位置。
子段 $$$a[l..r]$$$ 是所有元素 $$$a_l, a_{l + 1}, ..., a_r$$$。询问该子段后,您将获得该子段在整个数组中的第二个最大值的位置。
输入
第一行包含一个整数 $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — 数组中的元素数量。
互动
您可以通过打印“? $$$l$$$ $$$r$$$” $$$(1 \leq l < r \leq n)$$$ 来提出查询。答案是所有元素 $$$a_l, a_{l + 1}, ..., a_r$$$ 的第二个最大值的索引。数组 $$$a$$$ 是预先固定的,在交互时不能更改。
可以通过打印“!$$$p$$$”来输出答案,其中$$$p$$$是数组中最大元素的索引。
您最多可以提出 20 个疑问。打印答案不算作查询。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档
黑客
要进行破解,请使用以下测试格式。
在第一行输出一个整数 $$$n$$$ $$$(2 \leq n \leq 10^5)$$$。在第二行中输出 $$$n$$$ 整数 $$$1$$$ 到 $$$n$$$ 的排列。 $$$n$$$在排列中的位置就是最大值的位置
示例
输入 #1
5 3 4
输出 #1
? 1 5 ? 4 5 ! 1
注意
在示例中,假设 $$$a$$$ 为 $$$[5, 1, 4, 2, 3]$$$。因此,在询问$$$[1..5]$$$子段$$$4$$$之后,它是第二个最大值,它的位置是$$$3$$$。询问 $$$[4..5]$$$ 子段 $$$2$$$ 是第二个最大值,它在整个数组中的位置是 $$$4$$$。
请注意,还有其他数组 $$$a$$$ 会产生相同的交互,并且它们的答案可能不同。给出示例输出是为了理解交互。