Guess the tree

This is an interactive problem.

After the great battle that destroyed the planetary system Link-Cut, the local inhabitants asked you to help restore it. Unfortunately, almost all information about how it looked has disappeared. However, the wizard Frusy has once again come to your aid! He discovered a magical nebula that remembers how the system looked before the battle.

The Link-Cut planetary system can be represented as a tree consisting of $n$ vertices. For a single query to the nebula, you can provide a permutation of the tree vertices $p$. In response to the query, you receive an array $a$, where $a_i$ represents the number of connected components in the forest obtained by retaining only the vertices $p_1$, $p_2$, $\dots$, $p_i$.

Since each query costs Frusy a significant amount of mana, you are allowed to make at most $Q$ queries.

The interactor is not adaptive!

Input

The first line contains only one numbers $n(2\le n\le 2000)$.

Interaction

To perform the request, output "? $p_1$ $p_2$ $\dots$ $p_n$", where $p$ is a permutation.

In response to the request, the jury program will output an array $a$, where each element will be separated with the space.

If the request is invalid (i.e., the maximum number of requests has been exceeded or the request parameters are invalid), the jury program will output -1 and terminate. In this case, terminate your program to receive the verdict Wrong Answer.

Be sure to call the flush method after outputting each line. You can use:

• fflush(stdout), cout << endl, or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• sys.stdout.flush() in Python;

• consult the documentation for other programming languages.

Output

To give the answer, output in the first line "!", and in the next $n-1$ lines an edge, represented by two integers $u$ and $v$, of the tree in any order.

Examples

5

1 1 1 1 1

1 2 3 3 1

? 1 2 3 4 5

? 4 5 1 2 3

!
1 2 
4 3
3 1
3 5

Note

This image corresponds to the second query and a prefix of length $3$. We have highlighted the vertices $[4,5,1]$, resulting in $3$ connected components.

Scoring

1. ($12$ points): $n\le 100$, $Q=max(50,n^2)$;

2. ($13$ points): $n\le 200$, $Q=max(50,12n)$;

3. ($21$ points): $n\le 500$, $Q=max(50,2n+2)$;

4. ($32$ points): $n\le 1000$, $Q=max(50,n)$;

5. ($30$ points): The tree is a bamboo (each vertex has at most two neighbors), $Q=\lfloor \frac{n}{2}\rfloor +50$;

6. ($52$ points): $Q=\lfloor \frac{n}{2}\rfloor +50$;

7. ($90$ points): $Q=50$;