CF1486C1 Guessing the Greatest (easy version)

本题为交互题。 有一个长度为 $n$ 的数组 $a$，其中包含 $n$ 个互不相同的数。你可以进行一次查询，询问子区间 $a[l..r]$ 中的次大元素的位置。请在不超过 40 次查询的情况下，找出数组中最大元素的位置。 子区间 $a[l..r]$ 表示所有元素 $a_l, a_{l+1}, \ldots, a_r$。每次询问该子区间后，你将获得该子区间中次大元素在整个数组中的位置。

第一行包含一个整数 $n$ $(2 \leq n \leq 10^5)$，表示数组的长度。

你可以通过输出 "? $l$ $r$" $(1 \leq l < r \leq n)$ 进行一次查询，返回值为子区间 $a_l, a_{l+1}, \ldots, a_r$ 中次大元素在整个数组中的下标。数组 $a$ 在交互过程中不会发生变化。 当你确定最大元素的位置 $p$ 后，输出 "! $p$" 即可，其中 $p$ 是最大元素在数组中的下标。 你最多可以进行 40 次查询，输出答案不计入查询次数。 每次输出查询后请务必换行并刷新输出缓冲区，否则会导致“超出空闲时间限制”。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请参考相关文档 Hack 格式 制作 Hack 时，输入格式如下： 第一行输出一个整数 $n$ $(2 \leq n \leq 10^5)$。第二行输出 $n$ 个整数的一个排列，表示 $1$ 到 $n$ 的一个排列。排列中 $n$ 所在的位置即为最大值的位置。

例如，假设 $a = [5, 1, 4, 2, 3]$。如果你询问区间 $[1..5]$，则 $4$ 是次大值，其位置为 $3$。如果你询问区间 $[4..5]$，则 $2$ 是次大值，其在整个数组中的位置为 $4$。 注意，可能存在其他数组 $a$ 也能产生相同的交互过程，并且它们的答案可能不同。示例输出仅用于帮助理解交互过程。 由 ChatGPT 4.1 翻译