D. Последний рубеж

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

Перед ребятами дверь с $N$ замками. Некоторые замки открыты, некоторые закрыты, но какие именно — неизвестно. Потратив время на изучение одного замка, можно определить, открыт он или нет.

Замки пронумерованы слева направо числами от 1 до $N$. Самый левый замок открыт, самый правый закрыт. Чтобы открыть дверь, нужно найти замок с номером $i < N$ такой, что замок $i$ открыт, а замок $i + 1$ закрыт.

Осмотреть можно не более $Q = 60$ замков.

В начале на вход подаётся одно целое число $N$ ($2 \le N \le 10^{18}$).

После этого можно делать запросы вида ? i — осмотреть замок с номером $i$. В ответ приходит 0, если замок закрыт, и 1, если открыт.

Найдя ответ, выведите ! i и завершите работу. Состояние замков 1 и $N$ известно заранее.

После каждого запроса, в том числе последнего, выполняйте flush.

Ответ выводится запросом вида ! i.