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

Гомеру очень нравятся массивы, и он хочет поиграть с вами в игру. Гомер загадал перестановку $$$a_1, a_2, \dots, a_n$$$ чисел от $$$1$$$ до $$$n$$$. Вас просят найти любой индекс $$$k$$$ ($$$1 \leq k \leq n$$$), который является локальным минимумом.

Для массива $$$a_1, a_2, \dots, a_n$$$ индекс $$$i$$$ ($$$1 \leq i \leq n$$$) считается локальным минимумом, если $$$a_i < \min\{a_{i-1},a_{i+1}\}$$$, где $$$a_0 = a_{n+1} = +\infty$$$. Массив называется перестановкой чисел от $$$1$$$ до $$$n$$$, если он содержит все целые числа от $$$1$$$ до $$$n$$$ ровно один раз.

Изначально вам дается только значение $$$n$$$ без какой-либо другой информации об этой перестановке. На каждом шаге взаимодействия вы можете выбрать любой индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и сделать с ним запрос. В ответ вы получите значение $$$a_i$$$.

Вы должны найти любой индекс $$$k$$$, который является локальным минимумом, за не более чем $$$100$$$ запросов.

Вы начинаете взаимодействие с чтения целого числа $$$n$$$ ($$$1\le n \le 10^5$$$) в отдельной строке.

Чтобы сделать запрос с индексом $$$i$$$ ($$$1 \leq i \leq n$$$), необходимо в отдельной строке вывести «? $$$i$$$». Затем считайте в отдельной строке значение $$$a_i$$$. Количество запросов «?» должно не превышать $$$100$$$.

Чтобы вывести индекс $$$k$$$ ($$$1 \leq k \leq n$$$), который является локальным минимумом, выведите «! $$$k$$$» в отдельной строке и завершите вашу программу.

В случае, если ваш запрос имеет неверный формат, или вы сделали более $$$100$$$ запросов типа «?», вы получите вердикт Неправильный ответ.

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

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

Формат взломов

Первая строка взлома должна содержать единственное целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Вторая строка должна содержать попарно различные целые числа $$$n$$$ $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).