Description:
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 40 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.
Input Format:
The first line contains a single integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — the number of elements in the array.
Output Format:
None
Note:
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.