A13705. Chocolate Bunny

This is an interactive problem.

We hid from you a permutation $p$ of length $n$ , consisting of the elements from $1$ to $n$ . You want to guess it. To do that, you can give us 2 different indices $i$ and $j$ , and we will reply with $p_{i} \bmod p_{j}$ (remainder of division $p_{i}$ by $p_{j}$ ).

We have enough patience to answer at most $2 \cdot n$ queries, so you should fit in this constraint. Can you do it?

As a reminder, a permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ( $n=3$ but there is $4$ in the array).

The only line of the input contains a single integer $n$ ( $1 \le n \le 10^4$ ) — length of the permutation.

The interaction starts with reading $n$ .

Then you are allowed to make at most $2 \cdot n$ queries in the following way:

- "? x y" ( $1 \le x, y \le n, x \ne y$ ).

After each one, you should read an integer $k$ , that equals $p_x \bmod p_y$ .

When you have guessed the permutation, print a single line "! " (without quotes), followed by array $p$ and quit.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Exit immediately after receiving "-1" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Hack format

In the first line output $n$ ( $1 \le n \le 10^4$ ). In the second line print the permutation of $n$ integers $p_1, p_2, \ldots, p_n$ .