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

Изначально у вас есть массив $$$a = [1, 2, \ldots, n]$$$, где $$$n$$$ — нечетное натуральное число. Жюри выбрало $$$\frac{n-1}{2}$$$ непересекающихся пар элементов, и затем поменяло элементы в соответствующих парах местами. Например, если $$$a=[1,2,3,4,5]$$$, и были выбраны пары $$$1 \leftrightarrow 4$$$ и $$$3 \leftrightarrow 5$$$, то получился массив $$$[4, 2, 5, 1, 3]$$$.

Можно заметить, что в результате обменов ровно один элемент остался на своем месте. Вы должны найти этот элемент.

Чтобы сделать это, вы можете сделать несколько запросов. В каждом запросе вы выбираете два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$). В качестве ответа вы получите элементы подмассива $$$[a_l, a_{l + 1}, \dots, a_r]$$$, отсортированные по возрастанию.

Найдите элемент, оставшийся на своем месте. Вы можете сделать не более чем $$$\mathbf{15}$$$ запросов.

Массив $$$a$$$ зафиксирован до начала взаимодействия и не зависит от ваших запросов.

Массив $$$b$$$ является подмассивом $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Для каждого набора входных данных начните взаимодействие считыванием числа $$$n$$$.

Чтобы сделать запрос, выведите строку «$$$\texttt{?}\;l\;r$$$» ($$$1 \leq l \leq r \leq n$$$) без кавычек. После этого считайте $$$r-l+1$$$ целое число: числа $$$a_l, a_{l + 1}, \dots, a_r$$$ в возрастающем порядке. Вы можете сделать не более $$$15$$$ таких запросов для каждого набора входных данных.

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

Когда вы готовы дать ответ, выведите «$$$\texttt{!}\;x$$$» ($$$1 \leq x \leq n$$$) без кавычек — элемент, который остался на своем месте. Вывод ответа не учитывается в ограничении на $$$15$$$ запросов. После этого ваша программа должна продолжить решать оставшиеся наборы входных данных, или завершиться, если это был последний набор.

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

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

Взломы

Чтобы сделать взлом, используйте следующий формат. Первая строка должна содержать целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка каждого набора входных данных должна содержать одно целое число $$$n$$$ ($$$3 \leq n < 10^4$$$; $$$n$$$ нечетное) — длину массива $$$a$$$.

Вторая строка должна содержать $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$. Массив $$$a$$$ должен быть получен с помощью $$$\frac{n-1}{2}$$$ непересекающихся обменов позиций элементов из массива $$$[1,2,\dots,n]$$$.