ace5 and Task Order

这是一道交互题。 交互库会先生成一个长度为 $n$ 的 $1\sim n$ 排列与一个 $[1,n]$ 内的正整数 $x$。你需要通过询问确定整个排列。 你可以通过格式 `? i` 向交互库询问，返回值有三种： * `<`：代表 $a_i<x$，该次询问后，$x\leftarrow x-1$； * `>`：代表 $a_i>x$，该次询问后，$x\leftarrow x+1$； * `=`：代表 $a_i=x$。 如果你确定了整个排列，需要先输出 `!`，然后紧接着一行输出你的答案。 你的询问次数不应超过 $40n$，$n\leq 2000$。

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: - "&gt;", if $ a_i $ &gt; $ x $ , after which $ x $ will increase by $ 1 $ . - "&lt;", if $ a_i $ &lt; $ 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 $ .

2
5

>

=

<

=

<

<

2

>

? 4

? 2

? 1

? 5

? 1

? 3

! 2 4 1 5 3

? 1

! 2 1

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