408323: GYM103092 I I am Brain

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

Корпус Suleyman Demirel University состоит из $$$n$$$ учебных кабинетов, расположенных в один ряд и пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Новые перваши уже этой осенью поступят в наш чудесный универ, поэтому учитель программирования придумал классную задачку чтобы проверить их логику.

Ровно два кабинета из $$$n$$$ является кабинетами программирования. Скажем, что их номера — $$$a$$$ и $$$b$$$. Поскольку перваши в самом начале не будут знать номера этих кабинетов, учитель решил их загадать.

Все перваши подойдут к произвольному кабинету под номером $$$x$$$. Учитель, сидящий в этом кабинете, подскажет студентам сумму расстояний до кабинетов программирования. Более формально, он скажет им значение $$$|x - a| + |x - b|$$$. Затем перваши снова подойдут к произвольному кабинету $$$y$$$ и процесс будет повторяться до тех пор, пока перваши не будут уверены что нашли оба $$$a$$$ и $$$b$$$. Вполне возможно, что они в процессе уже посетят кабинет программирования, но хитрые учителя не станут это им раскрывать.

Алмас находится среди этих первашей. Он принял на себя роль мозга этой группы. Его цель — помочь своим одногруппникам найти $$$a$$$ и $$$b$$$ посетив как можно меньше кабинетов. Он уверен, что это возможно сделать за не более чем $$$50$$$ посещений. Помогите ему!

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

Далее программа будет отвечать на ваши запросы. Каждый запрос необходимо задавать в формате ? x ($$$1 \le x \le 10^9$$$). Перваши посетят кабинет под номером $$$x$$$. Затем нужно прочитать ответ учителя из стандартного ввода. Если учитель ответит $$$−1$$$ вместо корректного ответа, это означает, что перваши превысили $$$50$$$ посещений, или вы сделали некорректный запрос. Немедленно завершитесь после получения $$$−1$$$, чтобы получить вердикт Wrong answer. Иначе, вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.

Если вы угадали оба кабинета, выведите ответ в формате ! a b и завершите программу ($$$1 \le a < b \le n$$$).

После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

6

2

4

6

4

2

2

? 3

? 1

? 6

? 5

? 2

? 4

! 2 4