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

Жюри загадало перестановку$$$^\dagger$$$ $$$p$$$ длины $$$n$$$.

В один запрос можно выбрать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$), заплатив за это $$$(r - l)^2$$$ монет. В ответ вы получите количество инверсий$$$^\ddagger$$$ в подмассиве $$$[p_l, p_{l + 1}, \ldots p_r]$$$.

Найдите индекс максимального элемента в $$$p$$$, потратив не более $$$5 \cdot n^2$$$ монет.

Примечание: интерактор не является адаптивным: перестановка фиксируется до выполнения каких-либо запросов.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^\ddagger$$$ Количеством инверсий в массиве является количество пар индексов $$$(i,j)$$$ таких, что $$$i < j$$$ и $$$a_i > a_j$$$. Например, массив $$$[10,2,6,3]$$$ содержит $$$4$$$ инверсии: $$$(1,2),(1,3),(1,4)$$$ и $$$(3,4)$$$.

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

Для формирования запроса выведите «? l r» ($$$1 \le l < r \le n$$$) без кавычек. После этого вы должны прочитать одно единственное целое число — ответ на ваш запрос.

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

Когда вы будете готовы дать окончательный ответ, выведите «! i» ($$$1 \le i \le n$$$) без кавычек — индекс максимума загаданной перестановки. После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.

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

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

Взломы

Для взлома используйте следующий формат:

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2000$$$) — длина скрытой перестановки $$$p$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$), причем $$$p$$$ должно быть перестановкой.

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$2000$$$.