A16395. ace5 and Task Order

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.

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

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$ .

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$ .