B. Шляпа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Имур Ихаков организует клуб по шляпе. На клуб пришло принять участие n человек, где n чётно. Имур усадил их всех в круг и провёл жеребьевку, чтобы разбить ребят на пары, но что-то пошло не так. Участники пронумерованы так, что участники i и i + 1 (1 ≤ i ≤ n - 1) сидят рядом, а также участники n и 1 сидят рядом. Каждому был выдан листочек с числом так, что у ребят, сидящих рядом, эти числа отличаются ровно на единицу. Предполагалось, что игроки с одинаковыми числами образуют пару, но оказалось, что не все числа встречались ровно дважды.

Как известно, удобнее всего объяснять слова партнёру, когда он сидит напротив. Участники с номерами i и сидят напротив друг друга. Имуру интересно, есть ли люди, сидящие напротив друг друга и имеющие одинаковые числа на своих листочках. Помогите ему найти такую пару людей, если она есть.

Вы можете задавать вопросы вида «какое число написано на листочке у школьника i?». Ваша цель — выяснить, есть ли требуемая пара, сделав не более 60 вопросов.

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

На вход подаётся одно целое чётное число n (2 ≤ n ≤ 100 000) — число участников, пришедших на клуб Имура.

Вам разрешается задать не более 60 вопросов.

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

Для того, чтобы узнать число i-го участника (1 ≤ i ≤ n), нужно вывести «? i». После этого ваша программа на вход получит целое число ai ( - 109 ≤ ai ≤ 109) — число на листочке i-го человека.

Чтобы сообщить, что ответ найден, требуется вывести «! i», где i — номер любого участника из пары (1 ≤ i ≤ n). Если такой пары участников не существует, выведите «! -1». После этого программа должна завершиться.

Запрос на вывод ответа не входит в ограничение на 60 запросов.

Не забывайте сбрасывать буфер после каждого запроса. Например, на C++ надо использовать функцию fflush(stdout), на Java вызов System.out.flush(), на Pascal flush(output) и stdout.flush() для языка Python.

Взломы

Используйте следующий формат для взломов:

В первой строке выведите одно чётное целое число n (2 ≤ n ≤ 100 000) — количество школьников на клуб Имура.

Во второй строке выведите n чисел ai ( - 109 ≤ ai ≤ 109) разделённые пробелами, где ai — число, которое нужно написать на листочке i-му школьнику. Любые два соседних элемента, включая n и 1, должны отличаться на 1 или  - 1.

Взламываемое решение не будет иметь прямого доступа к последовательности ai.

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

2

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

? 4

? 8

! 4
Входные данные
6

1

2

3

2

1

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

? 1

? 2

? 3

? 4

? 5

? 6

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

Ввод-вывод в примерах демонстрирует пример взаимодействия.

В первом примере был загаданы результаты жеребьёвки соответствующие последовательности 1, 2, 1, 2, 3, 4, 3, 2

Во втором примере была загадана последовательность 1, 2, 3, 2, 1, 0.