C1. Найти наибольшее (простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

Входные данные

В первой строке находится единственное целое число $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — число элементов в массиве.

Протокол взаимодействия

Вы можете делать запросы посредством вывода «? $$$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$$$ в перестановке и будет позицией максимума.

Пример
Входные данные
5

3

4

Выходные данные
? 1 5

? 4 5

! 1
Примечание

В примере представьте, что $$$a$$$ это $$$[5, 1, 4, 2, 3]$$$. Так, после запроса подотрезка $$$[1..5]$$$ элемент со значением $$$4$$$ является вторым по значению и стоит на позиции $$$3$$$. После запроса подтрезка $$$[4..5]$$$ элемент со значением $$$2$$$ является вторым по значению и стоит на позиции $$$4$$$ во всём массиве.

Заметьте, что существуют другие массивы $$$a$$$, для которых интеракция выглядит точно также, а ответ может быть другим. Пример вывода дан для понимания интеракции.