H. Лучшая перестановка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

На математическом кружке учитель подготовил $$$n$$$ карточек с целыми числами и выложил их в ряд числами вниз. На $$$i$$$-й карточке написано число $$$a_i$$$, но ученики не знают этих чисел. После этого ученики играют с учителем в следующую игру.

У учеников есть $$$n$$$ жетонов с числами от $$$1$$$ до $$$n$$$, каждое число встречается ровно на одном жетоне. Ученики выполняют не более $$$n$$$ ходов. Каждый ход они выбирают перестановку $$$[p_1, p_2, \ldots, p_n]$$$ чисел от $$$1$$$ до $$$n$$$ и кладут жетоны на карточки, жетон с числом $$$p_i$$$ кладется на $$$i$$$-ю карточку. Учитель в ответ сообщает ученикам значение $$$$$$ S(p)=a_1p_1+a_2p_2+\ldots+a_np_n. $$$$$$

Цель учеников — получить максимальную возможную величину $$$S(p)$$$.

Напишите программу, которая будет играть в эту игру за учеников: сделает не более $$$n$$$ запросов и найдёт перестановку, для которой сумма $$$S(p)$$$ наибольшая. Если таких перестановок несколько, можно найти любую.

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

В первой строке дано целое число $$$n$$$ — длина скрытого массива ($$$1 \le n \le 500$$$).

Чтобы сделать запрос, выведите строку следующего вида:

? $$$p_1\ p_2\ \ldots\ p_n$$$
Числа $$$p_1, p_2, \ldots, p_n$$$ должны образовывать перестановку чисел от 1 до $$$n$$$. В ответ проверяющая программа выведет одно целое число — сумму $$$S(p)$$$. Считайте его перед следующим запросом. Всего разрешается сделать не более $$$n$$$ запросов. Гарантируется, что числа $$$a_i$$$ на карточках лежат в диапазоне от $$$-10^9$$$ до $$$10^9$$$.

Когда найдете перестановку с наибольшей возможной суммой, выведите строку следующего вида:

! $$$p_1\ p_2\ \ldots\ p_n$$$
После этого завершите программу. Окончательный ответ не считается запросом; ждать ответа на него не нужно.

Обязательно завершайте каждую строку переводом строки.

После вывода каждого запроса и окончательного ответа обязательно сбрасывайте буфер вывода: например, используйте cout « flush или endl в C++, print(..., flush=True) в Python. Один перевод строки без сброса буфера может привести к превышению времени ожидания.

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

21

10

20

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

? 3 1 2 4

? 2 4 1 3

? 4 2 3 1

? 1 3 4 2

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

В примере скрыт массив $$$(2, -1, 4, 2)$$$. В первом запросе выбрана перестановка $$$(3, 1, 2, 4)$$$, поэтому программа отвечает числом $$$2\cdot 3+(-1)\cdot 1+4\cdot 2+2\cdot 4=21$$$.

После четырех запросов выведен ответ $$$(2, 1, 4, 3)$$$. Для него сумма равна $$$2\cdot 2+(-1)\cdot 1+4\cdot 4+2\cdot 3=25$$$. Большую сумму получить нельзя. Перестановка $$$(3, 1, 4, 2)$$$ также является правильным ответом.

Пустые строки в таблице помогают показать порядок сообщений. Ваша программа выводит строки из правого столбца и читает ответы из левого.