CF1486C2.Guessing the Greatest (hard version)

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.

简单版本与困难版本的唯一区别在于查询次数的限制。

这是一道交互式题目。

存在一个包含 $n$ 个互不相同数字的数组 $a$。每次查询，你可以询问子段 $a[l..r]$ 中第二大的元素在该子段中的位置。你需要在不超过 20 次查询内，找出整个数组中最大元素的位置。

子段 $a[l..r]$ 包含所有元素 $a_l, a_{l + 1}, ..., a_r$。在你询问该子段后，系统将返回该子段中第二大的元素在整个数组中的位置。

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

第一行包含一个整数 $n$ $(2 \leq n \leq 10^5)$ —— 数组中元素的个数。

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.

在样例中，假设 $a$ 为 $[5, 1, 4, 2, 3]$。那么，在询问子段 $[1..5]$ 后，第二大的值是 $4$，其位置为 $3$；在询问子段 $[4..5]$ 后，第二大的值是 $2$，其在整个数组中的位置为 $4$。

注意，存在其他数组 $a$ 也能产生相同的交互过程，而它们的答案可能不同。给出该示例输出仅用于帮助理解交互过程。