Это интерактивная задача.
Имур Ихаков организует клуб по шляпе. На клуб пришло принять участие 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.
