CF1486C2 Guessing the Greatest (hard version)

本题的简单版与困难版唯一的区别在于查询次数的限制。 这是一个交互题。 有一个长度为 $n$ 的数组 $a$，其中包含 $n$ 个互不相同的数。每次查询，你可以询问某个子区间 $a[l..r]$ 中的次大元素的位置。请在不超过 $20$ 次查询内，找出数组中最大元素的位置。 子区间 $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..r]$ 中次大元素在整个数组中的下标。数组 $a$ 在交互过程中是固定不变的。 当你确定了最大元素的位置后，输出 "! $p$"，其中 $p$ 是最大元素在数组中的下标。 你最多只能进行 $20$ 次查询。输出答案不计入查询次数。 每次输出查询后，别忘了输出换行并刷新输出缓冲区，否则会导致“Idleness limit exceeded”错误。具体做法如下： - 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 翻译