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

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

Координатор загадывает число $$$x$$$ от $$$1$$$ до $$$n$$$.

ace5 может делать запросы типа: $$$?\ i$$$. Ответом будет:

• $$$>$$$, если $$$a_i > x$$$, после этого $$$x$$$ увеличивается на $$$1$$$.
• $$$<$$$, если $$$a_i < x$$$, после этого $$$x$$$ уменьшается на $$$1$$$.
• $$$=$$$, если $$$a_i = x$$$, после этого $$$x$$$ не меняется.

Задача ace5 — отгадать перестановку не более чем за $$$40n$$$ запросов. Так как ace5 слишком занят написанием анонса, он поручил эту задачу Вам.

Взаимодействие Вашей программы с программой жюри в каждом тестовом случае начинается со считывания целого положительного числа $$$n$$$ ($$$1 \leq n \leq 2000$$$) — длины загаданной перестановки.

Чтобы сделать запрос, выведите строку в формате «? i», где $$$1 \leq i \leq n$$$.

В качестве ответа вы получите:

• «>», если $$$a_i$$$ > $$$x$$$, после этого $$$x$$$ увеличится на $$$1$$$.
• «<», если $$$a_i$$$ < $$$x$$$, после этого $$$x$$$ уменьшится на $$$1$$$.
• «=», если $$$a_i$$$ = $$$x$$$, после этого $$$x$$$ не изменится.

Вы можете сделать не более $$$40n$$$ запросов. Чтобы вывести ответ, необходимо напечатать «! a_1 a_2 ... a_n», где $$$1 \leq a_i \leq n$$$, все они различны. Вывод ответа не считается за запрос.

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

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

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

Интерактор в этой задаче не является адаптивным.

Взломы:

Чтобы сделать взлом, используйте следующий формат:

В первой строке находится одно целое число $$$t$$$ — количество тестовых случаев.

Описание каждого тестового случая должно состоять из двух строк. В первой строке находятся числа $$$n$$$ и $$$x$$$ ($$$1 \leq x \leq n \leq 2000$$$) — длина загаданной перестановки и изначальное значение числа $$$x$$$. Во второй строке находятся $$$n$$$ различных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — перестановка, которую должно загадать жюри в данном тестовом случае.

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