L1. LCM Guess
time limit per test
12 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden permutation $$$P$$$ of length $$$n$$$ and you have to find it. For this, you have to choose two different integers $$$i$$$ and $$$j$$$, and the jury will give you $$$\text{lcm}(P_{i}, P_{j})$$$.

You can make no more than $$$2n+100$$$ queries in order to guess $$$P$$$.

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

Input

One integer $$$3\le n\le 10^5:$$$ The size of the hidden permutation $$$P$$$. Then, the interaction will start.

Interaction

After reading the length of the permutation $$$n,$$$ the interaction protocol is as follows :

  1. To get $$$\mathrm{lcm}(P_{i}, P_{j})$$$, output the query in the format $$$? \ \mathtt{i} \ \mathtt{j}$$$ where $$$1\le i\neq j \le n.$$$ You can make at most $$$2n+100$$$ queries.
  2. When you find $$$P$$$, output $$$P$$$ in the format $$$! \ \mathtt{P}_{1} \ \mathtt{P}_{2} \ \dots \ \mathtt{P}_{n}$$$. Printing the permutation is not counted as one of $$$2n+100$$$ operations.
  3. In the first occurrence of a query not conforming to the given format, you will receive $$$-1$$$, and you should exit immediately to get a Presentation error verdict.
Example
Input
3

3

6

2
Output

? 1 2

? 1 3 

? 2 3

! 3 1 2
Note

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

  • fflush(stdout) or cout.flush() in C++
  • fflush(stdout) in C
  • System.out.flush() in Java
  • stdout.flush() in Python