B. Доказательство неправоты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача. Не забывайте, что ваша программа должна каждый раз после вывода сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция.

Вася утверждает, что он изобрел алгоритм сортировки $$$n$$$-элементного массива $$$a$$$ (в котором все элементы различны), который делает меньше, чем $$$\lceil \log_2 (n!)\rceil$$$ сравнений!

Вася задаст вам не более $$$\lceil \log_2 (n!)\rceil - 1$$$ запросов вида: сравнить элементы $$$a_i$$$ и $$$a_j$$$. Вася утверждает, что данных запросов достаточно, чтобы отсортировать массив $$$a$$$, то есть, чтобы однозначно определить перестановку позиций массива $$$a$$$ от меньшего элемента к большему: $$$\operatorname{ord}_1, \operatorname{ord}_2, \dots, \operatorname{ord}_n$$$.

Ваша задача — найти перестановку позиций, отличающуюся от перестановки Васи, которая также согласуется со всеми запросами Васи.

Протокол взаимодействия

Изначально программа жюри отправит одно целое число $$$n$$$ ($$$3 \le n \le 18$$$) — размер массива.

Далее программа жюри отправит не более $$$\lceil \log_2 (n!)\rceil - 1$$$ запросов в следующем формате:

  • $$$?$$$ $$$i$$$ $$$j$$$ — сравнить $$$a_i$$$ и $$$a_j$$$ ($$$1 \le i, j \le n$$$; $$$i \ne j$$$).

На каждый запрос жюри ваша программа должна вывести <, если $$$a_i \lt a_j$$$, и > в противном случае.

После этого программа жюри отправит свой ответ в следующем формате:

  • $$$!$$$ $$$\operatorname{ord}_1 \operatorname{ord}_2 \dots \operatorname{ord}_n$$$

В ответ на это ваша программа должна вывести перестановку, отличную от перестановки жюри, которая согласуется со всеми предыдущими запросами, в аналогичном формате. Если возможных перестановок несколько, выведите любую из них. Обратите внимание, что массив $$$a$$$ выводить не нужно!

Если ваш ответ правильный, программа жюри отправит строку CORRECT в отдельной строке, указывая, что вы можете завершить программу. Если ответ неверен, программа жюри отправит строку ERROR в отдельной строке.

Если ваша программа нарушит формат запросов, жюри ответит строкой ERROR. В таком случае ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, потому что ваше решение продолжит читать из закрытого потока.

Не забывайте сбрасывать буфер вывода каждый раз, когда что-то выводите!

Пример
Входные данные
4
? 2 1

? 4 3

? 4 2

? 1 4

! 1 3 4 2

CORRECT
Выходные данные


>

>

<

<

! 3 1 4 2
Примечание

В примере из условия подходящим массивом $$$a$$$ мог быть, например, массив $$$3$$$ $$$9$$$ $$$0$$$ $$$7$$$. Этот массив подходит под все результаты сравнений, однако перестановка его элементов, предложенная алгоритмом Васи, не является его сортировкой.

Обратите внимание, что пробелы в примерах добавлены только для улучшения читаемости. При проверке решений интерактор пустых строк выводить не будет.