Josh is an egg inspector! One of his clients has $N$ varieties of eggs labelled from $1$ to $N$, living in a house with floors labelled from $1$ to $N$, bottom to top. The $i$-th variety of egg will shatter if and only if it is dropped from the floor $p_i$ or higher. It is guaranteed that $p_1,p_2,\dots ,p_N$ is a permutation of the integers from $1$ to $N$. Josh's job is to determine this hidden permutation.

Josh has unlimited eggs of each variety, and can test the eggs by dropping them from different floors in the house. Initially, he is in an elevator on floor $1$. In one move he can do one of the following:

• Drop an egg of a chosen variety from the current floor, and see whether it shatters or not.
• Move the elevator up or down by $1$ floor.

Additionally, the elevator is old, so it should not change directions frequently. Every time the direction of the elevator's movement is different to its previous movement's direction, an extra penalty of $20$ moves will be incurred.

Can you help Josh determine the permutation using as few moves as possible? You may drop at most $2\times {10}^5$ eggs.

Constraints

$2\le N\le {10}^4$

$p_1,p_2,\dots ,p_N$ is a permutation of the integers $1,2,\dots ,N$, generated uniformly at random.

Scoring

Let $M$ be the maximum number of moves made by your program in any test case. Your program will receive the following score:

$M$	Score
$0\le M\le 188000$	$100$
$188000<M\le 194000$	$\lfloor 100-\frac{M-188000}{600}\rfloor$
$194000<M\le 279800$	$\lfloor 90-\frac{M-194000}{1300}\rfloor$
$279800<M\le 400000$	$\lfloor 24-\frac{M-279800}{10000}\rfloor$
$400000<M\le {10}^8$	$5$
$M>{10}^8$	$0$

If your program fails to correctly guess the permutation in any test case, then you will receive $0$ points.

Interaction

This is an interactive problem. Note that the interactor is not adaptive.

At first, you should read in a single integer on a single line, representing the value of $N$.

Then, you will have the opportunity to make up to $2\times {10}^5$ queries. To make a query, output a line in the form ? e f. This corresponds to moving the elevator to floor $f$, and dropping an egg of the $e$-th variety. This will incur $|c-f|+1$ moves, where $c$ is the previous location of the elevator. Furthermore, if $c\ne f$ and the direction of the elevator's movement is different to its last movement's direction, $20$ additional moves will be incurred. Then, you should read in a single integer on a single line. This integer will be $1$ if the chosen egg shatters, and $0$ otherwise.

Finally, once you have made all of your queries, you should output a line in the form ! p_1 p_2 ... p_N, where $p$ is the permutation which you believe is the hidden permutation.

If at any point you format your queries incorrectly, or ask more than $2\times {10}^5$ queries, the interactor will respond with $-1$ on a single line. After receiving this feedback, you should terminate your program to receive a Wrong Answer verdict; otherwise, your program will receive an arbitrary verdict.

If you successfully guess the correct sequence, then you will receive an Accepted verdict for that test case. Your final score for the problem will be determined through the aforementioned scoring mechanism. You will be told the number of queries that you used.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

3
>>> ? 2 1
1
>>> ? 1 3
1
>>> ? 3 2
0
>> ! 2 1 3

Explanation

The hidden permutation is $2,1,3$.

For the first query, the elevator stays at floor $1$, and an egg of the $2$-nd variety is dropped, shattering. This query incurs $|1-1|+1=1$ move, since the elevator does not move, and a single egg is dropped.

For the second query, the elevator moves up from floor $1$ to $3$, and an egg of the $1$-st variety is dropped, shattering. This query incurs $|1-3|+1=3$ moves, since the elevator moves twice, and a single egg is dropped. Since this is the first movement of the elevator, no additional moves for changing direction are incurred.

For the third query, the elevator moves down from floor $3$ to $2$, and an egg of the $3$-rd variety is dropped, without shattering. This query incurs $|3-2|+1=2$ moves, since the elevator moves once, and a single egg is dropped. Since the elevator has changed direction from up to down, $20$ additional moves are incurred.

In total, $M=1+3+2+20=26$ moves have been made, and the permutation has been correctly guessed, so the score for this test case would be $100$.