P8320 "JROI-4" Sunset

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.

**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, $$d_i=\max_{j=1}^i \{a_j\}$$ 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.**

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

See “Interaction Format”.

**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](https://oi-wiki.org/contest/interaction/) **|** [Guess Number (IO Interactive Version) ](https://www.luogu.com.cn/problem/P1733) ------------ ## 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