Background

I cannot write nice text, so I will simply not include a background. [Background to be filled.]

Since this is only a C-level problem, the setter decided to be a bit more kind, so they added a few $0$ (meaning the number of interactions) (sure) — note from the reviewer.

Problem Description

This is an interactive problem.

Sunset can be abstracted as a sequence $\{a_n\}$.

$\{a_n\}$ is a permutation of $1 \sim n$.

You also have a sequence $\{d_n\}$, which is the prefix maximum of the current $a$ sequence.

In other words,

Note: According to the definition above, $\{d_n\}$ may change as the sequence $\{a_n\}$ changes.

You can perform two different operations:

• Specify an $i$, and ask: for the current $a$ sequence, how many distinct values are there in $d_{1\sim i}$.
• Specify an $i$, and set $a_i\leftarrow 0$.

Please determine the original permutation using no more than $5500$ operations.

It is guaranteed that the interactive library is static, i.e. the interactive library will not change the $a$ sequence during the interaction.

Input Format

This problem has multiple test cases. The first line contains an integer $T$, the number of test cases. Then follow $T$ lines, each containing an integer $n$, the length of the sequence in this test case.

This problem uses IO interaction mode.

Interaction Format

• ? 1 i Query how many distinct values there are in $d_{1\sim i}$. The interactive library returns a positive integer $x$ as the answer.

• ? 2 i Set $a_i=0$.

• ! a1 a2 a3 ... an Output the answer.

Note: In each test case, please make sure the total number of the first two types of operations does not exceed $5500$.

Also note that after each operation, you need to call the following function to flush the buffer:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);

For other languages, please check the corresponding language documentation.

Output Format

See “Interaction Format”.

1

3

1

2

3


2

? 1 1

? 1 2

? 1 3

? 2 2
? 1 3

! 1 2 3

Hint

The sample is only for understanding the interaction process and may not be logically consistent.

[Sample Explanation]

The initial sequence $a$ is 1 2 3, and $d$ is 1 2 3.

After outputting a command like ? 2 2 to the interactive library, the sequence $a$ becomes 1 0 3, and $d$ becomes 1 1 3. At this time, there are $2$ distinct values in $d_1\sim d_3$, namely $1,3$.

Reference materials for contestants: OI Wiki - Interactive Problems | Guess Number (IO Interactive Version)

Constraints

• For $10\%$ of the testdata, $T=1$.
• For $30\%$ of the testdata, $n\le 70$.
• For another $20\%$ of the testdata, the sequence $a$ is generated randomly.
• For all testdata: $T \leq 10,1\leq n\leq 500$.

Translated by ChatGPT 5