Задача . E. ace5 и порядок задач

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

В новом раунде было \(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\).