ace5 and Task Order
Contest: Codeforces Round 922 (Div. 2)
Difficulty rating: 2200
Tags: constructive algorithms, divide and conquer, implementation, interactive, probabilities, sortings

This is an interactive problem!

In the new round, there were $$$n$$$ tasks with difficulties from $$$1$$$ to $$$n$$$. The coordinator, who decided to have the first round with tasks in unsorted order of difficulty, rearranged the tasks, resulting in a permutation of difficulties from $$$1$$$ to $$$n$$$. After that, the coordinator challenged ace5 to guess the permutation in the following way.

Initially, the coordinator chooses a number $$$x$$$ from $$$1$$$ to $$$n$$$.

ace5 can make queries of the form: $$$?\ i$$$. The answer will be:

- $$$>$$$, if $$$a_i > x$$$, after which $$$x$$$ increases by $$$1$$$.
- $$$<$$$, if $$$a_i < x$$$, after which $$$x$$$ decreases by $$$1$$$.
- $$$=$$$, if $$$a_i = x$$$, after which $$$x$$$ remains unchanged.

The task for ace5 is to guess the permutation in no more than $$$40n$$$ queries. Since ace5 is too busy writing the announcement, he has entrusted this task to you.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

Interaction format:
The interaction between your program and the jury's program begins with reading a positive integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the length of the hidden permutation.

To make a query, output a line in the format "? i", where $$$1 \leq i \leq n$$$.

As an answer, you will receive:

- ">", if $$$a_i$$$ > $$$x$$$, after which $$$x$$$ will increase by $$$1$$$.
- "<", if $$$a_i$$$ < $$$x$$$, after which $$$x$$$ will decrease by $$$1$$$.
- "=", if $$$a_i$$$ = $$$x$$$, after which $$$x$$$ will remain unchanged.

You can make no more than $$$40n$$$ queries. To output the answer, you need to print "! a_1 a_2 ... a_n", where $$$1 \leq a_i \leq n$$$, and all of them are distinct. Outputting the answer does not count as a query.

If your program makes more than $$$40n$$$ queries for one test case, or makes an invalid query, then the response to the query will be -1. After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After outputting a query, do not forget to print a newline and flush the output buffer. Otherwise, you will receive the verdict Presentation Error. To flush the buffer, use:

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

The interactor in this problem is not adaptive.

Hacks:

To make a hack, use the following format:

The first line contains a single integer $$$t$$$ — the number of test cases.

The description of each test case should consist of two lines. The first line contains the numbers $$$n$$$ and $$$x$$$ ($$$1 \leq x \leq n \leq 2000$$$) — the length of the hidden permutation and the initial value of the number $$$x$$$. The second line contains $$$n$$$ distinct numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the permutation that the jury should choose in this test case.

Sum of $$$n$$$ over all test cases should not exceed $$$2000$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, the hidden permutation is $$$a$$$ = [$$$2,4,1,5,3$$$], and the initial value of $$$x$$$ is $$$3$$$.

In the second test, the hidden permutation is $$$a$$$ = [$$$2,1$$$], and the initial value of $$$x$$$ is $$$1$$$.

Example input:
2
5

>

=

<

=

<

<

2

>

Example output:
? 4

? 2

? 1

? 5

? 1

? 3

! 2 4 1 5 3

? 1

! 2 1

Editorial:
Randomized solution: We will use the quicksort algorithm. We will choose a random element from the array, let its index be $$$i$$$, and we will perform $$$? i$$$ until we get the answer $$$=$$$ (i.e., $$$x = a_i$$$). Now we will ask about all the other elements, thereby finding out whether they are greater than or less than $$$a_i$$$ (don't forget to return $$$x = a_i$$$, i.e., perform $$$? i$$$ after each query about the element). After this, we will divide all the elements into two parts, where $$$a_i > x$$$ and $$$a_i < x$$$. We will recursively run the algorithm on each part. The parts will become smaller and smaller, and in the end, we will sort our permutation, allowing us to guess it. Non-randomized solution: We will find the element $$$1$$$ in the array in $$$3*n$$$ queries. To do this, we will go through the array, asking about each element each time. If the answer is $$$<$$$, we will continue asking until the answer becomes $$$=$$$, and if the answer is $$$=$$$ or $$$>$$$, we will move on to the next element. Then the last element on which the answer was $$$<$$$ is the element $$$1$$$. $$$x$$$ will increase by a maximum of $$$n$$$ in the process (a maximum of $$$1$$$ from each element), so it will decrease by a maximum of $$$2*n$$$, i.e., a maximum of $$$3*n$$$ queries. Similarly, we will find the element $$$n$$$. Now we will run an algorithm similar to the randomized solution, but now we can set $$$x = n/2$$$ instead of taking $$$x$$$ as a random element. Both solutions comfortably fit within the limit of $$$40n$$$ queries.