Это интерактивная задача. Не забывайте, что ваша программа должна каждый раз после вывода сбрасывать буфер вывода. Для сброса буфера вывода можно использовать 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$$$ запросов в следующем формате:
На каждый запрос жюри ваша программа должна вывести <, если $$$a_i \lt a_j$$$, и > в противном случае.
После этого программа жюри отправит свой ответ в следующем формате:
В ответ на это ваша программа должна вывести перестановку, отличную от перестановки жюри, которая согласуется со всеми предыдущими запросами, в аналогичном формате. Если возможных перестановок несколько, выведите любую из них. Обратите внимание, что массив $$$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$$$. Этот массив подходит под все результаты сравнений, однако перестановка его элементов, предложенная алгоритмом Васи, не является его сортировкой.
Обратите внимание, что пробелы в примерах добавлены только для улучшения читаемости. При проверке решений интерактор пустых строк выводить не будет.