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

Во время обеденного перерыва Алиса и Боб играют в игру. У них имеется бамбук из $$$n$$$ вершин. Бамбук это такой граф, где $$$n-1$$$ ребро вида $$$(1,2), (2,3), \dots, (n-1,n)$$$. Боб мысленно провёл дополнительное ребро между вершинами $$$a$$$ и $$$b$$$, не сообщая их Алисе. При чём Боб выбрал $$$a,b$$$ так, что $$$a + 2 \le b$$$. Все рёбра являются неориентированными.

Алисе необходимо выяснить, какие конкретно вершины соединил ребром Боб. Для этого она может его спрашивать, правда ли, что между вершинами $$$l_i, r_i$$$ кратчайший путь проходит через ребро, которое провёл Боб.

Помогите Алисе выиграть у Боба, выяснив искомое ребро при помощи вопросов. Так как обеденный перерыв короткий, то Алиса успеет задать не более $$$50$$$ вопросов.

В начале на вход программе подаётся одно целое число $$$n$$$ ($$$5 \le n \le 10^6$$$) — количество вершин в бамбуке.

После этого вы можете делать запросы вида ? l r, означающие, что Алиса спрашивает, лежит ли искомое ребро на кратчайшем пути между $$$l$$$, $$$r$$$. В ответ на подобный запрос вы получите число 1, означающее, что гарантированно ребро находится на кратчайшем пути, то есть путь через добавленное ребро строго короче, чем любой из путей без него, 0 иначе.

Если вы нашли ответ, вы должны сделать запрос вида ! l r, означающий, что вы считаете, что Боб провёл ребро между вершинами $$$l$$$ и $$$r$$$. После этого запроса вы должны завершить работу программы.

Вы должны сделать не более $$$50$$$ запросов первого типа. В случае превышения этого ограничения ваше решение получит вердикт «Неправильный ответ».

В случае нарушения каких-либо правил взаимодействия с программой-интерактором ваше решение может получить любой вердикт.

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

Для сброса буфера вывода (то есть для операции 'flush') сразу после вывода запроса и перевода строки нужно сделать:

• fflush(stdout) или cout.flush() или cout « endl в языке C++;
• System.out.flush() в Java;
• stdout.flush() в Python;

Если вы не сделаете операцию flush, как и если не выведите перевод строки после какого-либо запроса, ваше решение может получить любой вердикт.