Это интерактивная задача.
На математическом кружке учитель подготовил $$$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$$$).
Чтобы сделать запрос, выведите строку следующего вида:
Когда найдете перестановку с наибольшей возможной суммой, выведите строку следующего вида:
Обязательно завершайте каждую строку переводом строки.
После вывода каждого запроса и окончательного ответа обязательно сбрасывайте буфер вывода: например, используйте 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)$$$ также является правильным ответом.
Пустые строки в таблице помогают показать порядок сообщений. Ваша программа выводит строки из правого столбца и читает ответы из левого.