CF1812H.Expected Twist

这是一个交互题。

有一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$，你无法直接看到数组内容。你的任务是找出该数组中的最小元素。

为此，你可以进行若干次查询。每次查询时，你可以选择两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）。系统会返回 $\max(a_l, a_{l+1}, \dots, a_r)$ 的值，也就是子数组 $a_l$ 到 $a_r$ 的最大值。

请找出该数组的最小值。你最多可以进行 $624$ 次查询。

保证 $a_1, a_2, \dots, a_n$ 的值均匀随机地选自 $0$ 到 $2^{32}-1$（包含端点）。

首先，读入一个整数 $n$（$1 \leq n \leq 10^4$），表示数组的长度。

每次你想进行查询时，输出一行 $\texttt{?}\;\;l\;\;r$（$1 \leq l \leq r \leq n$）。然后你需要读入一行，包含该查询的答案。

当你确定了答案后，输出一行 $\texttt{!}\;\;x$，其中 $x$ 是数组的最小值。

每次输出查询后，不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 的判罚。具体做法如下：

• C++：使用 fflush(stdout) 或 cout.flush()；
• Java：使用 System.out.flush()；
• Pascal：使用 flush(output)；
• Python：使用 stdout.flush()；
• 其它语言请参考相关文档。

如果收到的答案为 $-1$，说明你的查询无效。此时应立即退出程序，你会收到 Wrong answer 的判罚。否则，如果继续读取输入流，你可能会收到任意判罚结果。

见输入格式说明。

无。

由 ChatGPT 4.1 翻译