Guessing the Greatest (hard version)

题意翻译

这是一道交互题。 有一个**数字各不相同**长度为 $n(2\leq n\leq 10^5$ 的数组 `a`，在一个查询中，您可以询问子段 $a[l...r]$ 中**次大值（第二大的值）**的位置。您需要在不超过 `20` 个查询中查找数组中最大元素的位置。 您可以通过输出 $"? \;l\; r"(1\leq l \leq r\leq n)$ 询问,结果是从 `l` 到`r`中次大值的位置。数组事先已生成，无法在交互时更改。 您可以通过输出 $"!\; p"$，在那里是数组中最大元素的坐标。 您可以进行不超过 `20`个查询。输出答案不算作查询。 请注意，样例仅用来表示交互的规则，不保证有逻辑性。 感谢@[听取MLE声一片](https://www.luogu.com.cn/user/253738) 提供翻译

题目描述

The only difference between the easy and the hard version is the limit to the number of queries. This is an interactive problem. There is an array $ a $ of $ n $ different numbers. In one query you can ask the position of the second maximum element in a subsegment $ a[l..r] $ . Find the position of the maximum element in the array in no more than 20 queries. A subsegment $ a[l..r] $ is all the elements $ a_l, a_{l + 1}, ..., a_r $ . After asking this subsegment you will be given the position of the second maximum from this subsegment in the whole array.

输入输出格式

输入格式

The first line contains a single integer $ n $ $ (2 \leq n \leq 10^5) $ — the number of elements in the array.

输出格式

You can ask queries by printing "? $ l $ $ r $ " $ (1 \leq l < r \leq n) $ . The answer is the index of the second maximum of all elements $ a_l, a_{l + 1}, ..., a_r $ . Array $ a $ is fixed beforehand and can't be changed in time of interaction. You can output the answer by printing "! $ p $ ", where $ p $ is the index of the maximum element in the array. You can ask no more than 20 queries. Printing the answer doesn't count as a query. After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages Hacks To make a hack, use the following test format. In the first line output a single integer $ n $ $ (2 \leq n \leq 10^5) $ . In the second line output a permutation of $ n $ integers $ 1 $ to $ n $ . The position of $ n $ in the permutation is the position of the maximum

输入输出样例

输入样例 #1

5

3

4

输出样例 #1

? 1 5

? 4 5

! 1

说明

In the sample suppose $ a $ is $ [5, 1, 4, 2, 3] $ . So after asking the $ [1..5] $ subsegment $ 4 $ is second to max value, and it's position is $ 3 $ . After asking the $ [4..5] $ subsegment $ 2 $ is second to max value and it's position in the whole array is $ 4 $ . Note that there are other arrays $ a $ that would produce the same interaction, and the answer for them might be different. Example output is given in purpose of understanding the interaction.