Единственная разница в легкой и сложной версии это ограничение на количество запросов.

Это интерактивная задача.

Есть массив $$$a$$$ из $$$n$$$ различных чисел. За один запрос вы можете узнать позицию второго максимума на подотрезке $$$a[l..r]$$$. Найдите позицию максимального элемента в массиве за не более чем 40 запросов.

Подотрезком $$$a[l..r]$$$ называются все элементы $$$a_l, a_{l + 1}, ..., a_r$$$. После запроса этого подотрезка на ввод вы получите позицию второго максимума из этого подотрезка во всём массиве.

Вы можете делать запросы посредством вывода «? $$$l$$$ $$$r$$$» $$$(1 \leq l < r \leq n)$$$. Ответом будет выведена позиция второго максимума среди элементов $$$a_l, a_{l + 1}, \ldots, a_r$$$. Массив $$$a$$$ заранее зафиксирован и не может быть изменен во время интеракции.

Вы можете вывести ответ, выведя «! $$$p$$$», где $$$p$$$ — индекс максимального элемента во всем массиве.

Вы можете сделать не более 40 запросов. Вывод ответа не считается за запрос.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы

Для того, чтобы сделать взлом, используйте следующий формат теста.

В первой строке выведите одно целое число $$$n$$$ $$$(2 \leq n \leq 10^5)$$$. Во второй строке выведите перестановку $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$. Позиция числа $$$n$$$ в перестановке и будет позицией максимума.