H. Best Permutation
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

At a math club, the teacher prepared $$$n$$$ cards with integers and laid them out in a row face down. The number written on the $$$i$$$-th card is $$$a_i$$$, but the students do not know these numbers. Then the students play the following game with the teacher.

The students have $$$n$$$ tokens numbered from $$$1$$$ to $$$n$$$, with each number appearing on exactly one token. The students make at most $$$n$$$ moves. In each move, they choose a permutation $$$[p_1, p_2, \ldots, p_n]$$$ of the numbers from $$$1$$$ to $$$n$$$ and place the tokens on the cards, with the token numbered $$$p_i$$$ placed on the $$$i$$$-th card. In response, the teacher tells the students the value $$$$$$ S(p)=a_1p_1+a_2p_2+\ldots+a_np_n. $$$$$$

The goal of the students is to obtain the maximum possible value of $$$S(p)$$$.

Write a program that will play this game for the students: it should make at most $$$n$$$ queries and find a permutation for which the sum $$$S(p)$$$ is maximum. If there are several such permutations, you may find any of them.

Interaction

The first line contains an integer $$$n$$$ — the length of the hidden array ($$$1 \le n \le 500$$$).

To make a query, output a line of the following form:

? $$$p_1\ p_2\ \ldots\ p_n$$$
The numbers $$$p_1, p_2, \ldots, p_n$$$ must form a permutation of the numbers from 1 to $$$n$$$. In response, the judging program will output one integer — the value of $$$S(p)$$$. Read it before making the next query. In total, you are allowed to make at most $$$n$$$ queries. It is guaranteed that the numbers $$$a_i$$$ on the cards lie in the range from $$$-10^9$$$ to $$$10^9$$$.

When you find a permutation with the maximum possible sum, output a line of the following form:

! $$$p_1\ p_2\ \ldots\ p_n$$$
Then terminate your program. The final answer is not counted as a query; you do not need to wait for a response to it.

Be sure to end every line with a newline character.

After outputting each query and the final answer, you must flush the output buffer: for example, use cout « flush or endl in C++, print(..., flush=True) in Python. A newline without flushing may lead to a time limit exceeded error.

Example
Input
4

21

10

20

19
Output

? 3 1 2 4

? 2 4 1 3

? 4 2 3 1

? 1 3 4 2

! 2 1 4 3
Note

In the example, the hidden array is $$$(2, -1, 4, 2)$$$. In the first query, the permutation $$$(3, 1, 2, 4)$$$ is chosen, so the program responds with the number $$$2\cdot 3+(-1)\cdot 1+4\cdot 2+2\cdot 4=21$$$.

After four queries, the answer $$$(2, 1, 4, 3)$$$ is output. For it, the sum is $$$2\cdot 2+(-1)\cdot 1+4\cdot 4+2\cdot 3=25$$$. A larger sum cannot be obtained. The permutation $$$(3, 1, 4, 2)$$$ is also a correct answer.

Empty lines in the table help show the order of messages. Your program outputs the lines from the right column and reads the responses from the left column.