A. Угадай число

Это интерактивная задача. Интерактор адаптивный.

Жюри загадало целое число от 1 до $n$. Вы можете спрашивать про любое число $x$, и жюри отвечает, больше загаданное, меньше или равно. Угадайте загаданное не более чем за 30 вопросов.

В начале взаимодействия считайте одно число $n$ ($1 \le n \le 10^9$) — верхнюю границу загаданного.

Чтобы задать вопрос, выведите строку ? x ($1 \le x \le n$). В ответ придёт одно число:

• 1 — загаданное больше $x$;
• -1 — загаданное меньше $x$;
• 0 — загаданное равно $x$; после этого ответа завершите работу.

Вопросов не больше 30. После каждого вывода делайте flush.