这是一个交互问题。
有一个数组 $$$a_1, a_2, \dots, a_n$$$ 个 $$$n$$$ 整数对你隐藏。你的任务是找到数组的最小元素。
为此,您可以询问几个问题。在每个查询中,您可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$)。作为回报,您将获得 $$$\max(a_l, a_{l+1}, \dots, a_r)$$$ 的值。换句话说,您将被告知从 $$$a_l$$$ 到 $$$a_r$$$ 的子数组的最大值。
找到数组的最小值。您最多可以提出 $$$\mathbf{624}$$$ 查询。
保证 $$$a_1, a_2, \dots, a_n$$$ 值在 $$$0$$$ 和 $$$2^{32}-1$$$(含)之间均匀随机选择。
互动
通过读取单独一行上的整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) 开始交互。
要提出查询,请以 $$$\texttt{?}\;\;l\;\;r$$$ ($$$1 \le l \le r \le n$$$) 的形式打印一行。然后您应该阅读包含查询答案的一行。
确定答案后,以 $$$\texttt{!}\;\;x$$$ 的形式打印一行,其中 $$$x$$$ 是最小值。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
回答 $$$\texttt{-1}$$$ 表示您进行了无效查询。收到$$$\texttt{-1}$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
示例
输入 #1
3 1295320727 984617979 1295320727 167316954
输出 #1
? 1 3 ? 1 1 ? 2 2 ? 3 3 ! 167316954