G. Guess The Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Sultan Shahrayar has $$$n$$$ advisors, numbered from $$$1$$$ to $$$n$$$. One time he was bored, so he arranged them in a line, ordered from the wisest to the least wise. To test your intelligence, he brings you to his castle and challenges you to guess the exact order of the advisors. To help you, he allows you to ask $$$20000$$$ questions. In each question, you can pick a number $$$x$$$ and Shahrayar will tell you whether the number of inversions of the order is more or less or equal to $$$x$$$.

A pair $$$(i, j)$$$ is called an inversion in an array $$$A$$$ of length $$$n$$$ if:

  • $$$1 \le i \lt j \le n$$$ and $$$A_i$$$ > $$$A_j$$$.

After each question, the order of the advisors is rotated to the right.

For example, if the initial order is $$$[4, 1, 3, 2]$$$, the inversions are $$$(4,1)$$$, $$$(4,3)$$$, $$$(4,2)$$$, and $$$(3,2)$$$, resulting in a total of $$$4$$$ inversions. After one question, the order becomes $$$[2, 4, 1, 3]$$$ and the number of inversions is $$$3$$$.

Interaction

The interaction starts after reading a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$ - the length of the permutation.

To ask a question, print "$$$?$$$ $$$x$$$" $$$(0 \le x \le n^2)$$$, then read the answer.

  • You will receive $$$ \lt $$$ if the number of inversions of the order is less than $$$x$$$.

  • You will receive $$$=$$$ if the number of inversions of the order is equal to $$$x$$$.

  • You will receive $$$ \gt $$$ if the number of inversions of the order is greater than $$$x$$$.
If you guess the permutation, print "$$$!$$$ $$$p_{1}$$$ $$$p_{2}...p_{n}$$$"
Example
Input
3

<

<

>

=
Output

? 2

? 2

? 2

? 1

! 1 3 2
Note

You have to guess the initial order, not the order after the questions.

After printing a query or the answer, do not forget to output an 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;

- stdout.flush() in Python;