Это интерактивная задача.
VegiCat загадал массив $a_1, a_2, \ldots, a_n$, каждый элемент которого равен $0$, $1$ или $2$. Он не хочет сообщать вам значения элементов, но вы можете задавать ему вопросы. В каждом запросе вы выбираете два индекса $i$ и $j$, а VegiCat сообщает вам, верно ли, что $a_i > a_j$.
VegiCat просит вас вывести индексы в порядке неубывания соответствующих значений массива. Иными словами, найдите такую перестановку $p_1, p_2, \ldots, p_n$ чисел $1, 2, \ldots, n$, что
$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$
В каждом наборе входных данных вы можете сделать не более $2n - 3$ запросов.
Интерактор адаптивен. Это означает, что массив не зафиксирован заранее. Интерактор гарантирует, что в любой момент существует хотя бы один массив с элементами из $\{0, 1, 2\}$, согласующийся со всеми данными до сих пор ответами. Ваша итоговая перестановка должна быть корректной для любого массива, согласующегося со всеми ответами.
Входные данные
Первая строка содержит целое число $T$ ($1 \le T \le 250$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Каждый набор входных данных начинается с целого числа $n$ ($2 \le n \le 500$) — длины массива.
Сумма $n$ по всем наборам входных данных не превосходит $500$.
Протокол взаимодействия
Чтобы сделать запрос, выведите строку в следующем формате:
? i j
Здесь $1 \le i, j \le n$. После каждого запроса считайте одно целое число:
- $1$, если $a_i > a_j$;
- $0$, если $a_i \le a_j$.
Запросы с $i = j$ и повторные запросы разрешены и учитываются в общем количестве запросов.
Когда вы определите порядок, выведите строку в следующем формате:
! p_1 p_2 ... p_n
Каждый индекс от $1$ до $n$ должен встретиться ровно один раз. Вывод ответа не считается запросом.
Если ваш ответ верен, переходите к следующему набору входных данных, считав его число $n$, или завершите работу программы, если это был последний набор входных данных. Интерактор не отправляет отдельного подтверждения после ответа.
После вывода каждого запроса или ответа выводите перевод строки и сбрасывайте буфер вывода (flush). Для сброса буфера вывода можно использовать:
fflush(stdout)илиcout.flush()в C/C++;System.out.flush()в Java и Kotlin;sys.stdout.flush()в Python.
Если вы сделаете некорректный запрос, превысите лимит запросов или выведете неправильный ответ, вы получите вердикт Wrong Answer. Вывод, не соответствующий указанному формату, также оценивается вердиктом Wrong Answer. В этих случаях интерактор завершает работу без отправки сообщения об ошибке.
Примеры
Входные данные 1
2 3 1 1 2 0
Выходные данные 1
? 1 2 ? 2 3 ! 3 2 1 ? 1 2 ! 1 2
Примечание
В первом наборе входных данных запросы ? 1 2 и ? 2 3 оба возвращают $1$, поэтому $a_1 > a_2 > a_3$. Следовательно, $(3, 2, 1)$ — правильный ответ.
Во втором наборе входных данных запрос ? 1 2 возвращает $0$, поэтому $a_1 \le a_2$. Следовательно, $(1, 2)$ — правильный ответ.