Это интерактивная задача.
Гомеру очень нравятся массивы, и он хочет поиграть с вами в игру. Гомер загадал перестановку \(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\)).
Примечание
В примере в первой строке содержится целое число \(5\), указывающее на то, что длина массива составляет \(n = 5\).
В примере делается пять запросов «?», после которых мы делаем вывод, что массив равен \(a = [3,2,1,4,5]\) и \(k = 3\) является локальным минимумом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
2
1
4
5
|
? 1
? 2
? 3
? 4
? 5
! 3
|