CF1918E.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:

• $ \gt $, if $a_i \gt x$, after which $x$ increases by $1$.
• $ \lt $, if $a_i \lt 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.

这是一个交互式问题！

在新一轮比赛中，共有 $n$ 道题目，难度分别为 $1$ 到 $n$。出题人决定让第一轮的题目按难度非升序/非降序排列，于是将题目重新排序，得到一个 $1$ 到 $n$ 的排列（即难度的一个排列）。之后，出题人向 ace5 提出挑战：让他猜出该排列，规则如下。

初始时，出题人选定一个数 $x$，其取值范围为 $1$ 到 $n$。

ace5 可以进行形如 $?\ i$ 的查询。系统将返回以下三种回答之一：

• $ \gt $，若 $a_i \gt x$；此后 $x$ 增加 $1$；
• $ \lt $，若 $a_i \lt x$；此后 $x$ 减少 $1$；
• $=$，若 $a_i = x$；此后 $x$ 保持不变。

ace5 的任务是在不超过 $40n$ 次查询内猜出整个排列 $a$。由于 ace5 正忙于撰写比赛公告，他已将此任务托付给你。

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

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。

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

在第一次测试中，隐藏的排列为 $a$ = [$2,4,1,5,3$]，且 $x$ 的初始值为 $3$。

在第二次测试中，隐藏的排列为 $a$ = [$2,1$]，且 $x$ 的初始值为 $1$。