У Стивена есть $$$n$$$ гаек и $$$n$$$ болтов. Все гайки имеют разный размер от 1 до $$$n$$$, и все болты имеют разный размер от 1 до $$$n$$$.
Стивен может за одно действие попробовать надеть одну из гаек на один из болтов. В результате этого действия он выяснит, размер гайки больше, размер болта больше или же эти гайка и болт имеют одинаковый размер. Он хочет определить для каждого болта, какая гайка ему подходит.
Вы должны помочь Стивену осуществить задуманное, затратив не более $$$5 n \log_{2}n$$$ действий.
Это интерактивная задача. Ваша программа должна общаться с программой жюри, используя для этого стандартные потоки ввода и вывода.
В самом начале вашей программе сообщается целое число $$$n$$$ ($$$2 \le n \le 1000$$$) — количество гаек и болтов.
После этого вы можете сделать не более $$$5 n \log_{2}n$$$ запросов. Чтобы сделать запрос, выведите символ «?», а затем через пробел числа $$$i$$$ и $$$j$$$ ($$$1 \le i \le n, 1 \le j \le n$$$) — номер гайки и номер болта, которые Стивен попробует сравнить.
В ответ на такой запрос вы получите один из трех символов:
Как только вы сможете сказать, какая гайка подходит на какой болт, выведите символ «!», а через пробел $$$n$$$ различных целых чисел $$$p_i$$$ ($$$1 \le p_i \le n$$$), где $$$p_i$$$ — это номер болта, на который подходит гайка с номером $$$i$$$. После этого ваша программа должна завершиться.
5 < < > > < = = = = =
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 1 4 ? 2 3 ? 3 2 ? 4 5 ? 5 1 ! 4 3 2 5 1
Обратите внимание, что каждое выведенное вами сообщение должно завершаться переводом строки. Также после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы «fflush(stdout)» или «cout.flush()» в C++, «System.out.flush()» в Java, «Console.Out.Flush()» в C#, «flush(output)» в Pascal, «sys.stdout.flush()» в Python.
Пустые строки в примере приведены лишь для удобства, чтобы было лучше понятно, в каком порядке выводятся сообщения. При решении задачи вам не нужно выводить пустые строки, и программа жюри тоже не будет выводить пустые строки.
