[EC Final 2022] Inversion

**【题目描述】** 这是一个交互式问题。 有一个隐藏的排列 $p_1, p_2, \dots, p_n$，其中包含 $\{1, 2, \dots, n\}$ 的排列。你想通过询问 $p_l,\ldots, p_r$ 的逆序对数量的奇偶性来找到它。 你可以以 ${?~l~r}$ 的格式进行查询，交互器会回答你 $\left( \sum_{l\leq i < j\leq r} [p_i > p_j]\right) \bmod 2$。其中 $[p_i>p_j]$ 在 $p_i>p_j$ 时为 $1$，在 $p_i\le p_j$ 时为 $0$。 首先，你需要读入整数 $n$（$1\le n\le 2000$）。 之后，你可以进行不超过 $4 \times 10^4$ 次查询。要进行查询，输出 ${?~l~r}$（$1 \leq l \leq r \leq n$）在单独的一行上，然后你应该从标准输入中读取响应。 要给出你的答案，将 ${!~p_1~p_2~\dots~p_n}$ 打印在单独的一行上。答案的输出 $\textbf{不}$ 计入 $4 \times 10^4$ 次查询的限制。 之后，你的程序应该终止。 在打印查询后，不要忘记输出换行并刷新输出。要做到这一点，在 C++ 中使用 $\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$，在 Java 中使用 $\texttt{System.out.flush()}$，在 Pascal 中使用 $\texttt{flush(output)}$，或者在 Python 中使用 $\texttt{stdout.flush()}$。 保证排列提前固定。 翻译来自于：[ChatGPT](https://chatgpt.com/)

$\textbf{This is an interactive problem.}$ There is a hidden permutation $p_1, p_2, \dots, p_n$ of $\{1, 2, \dots, n\}$. You want to find it by asking the parity of the number of inversions of $p_l,\ldots, p_r$. You can query in the format ${?~l~r}$, and the interactor will respond you $\left( \sum_{l\leq i < j\leq r} [p_i > p_j]\right) \bmod 2$. $[p_i>p_j]$ is $1$ when $p_i>p_j$ and $0$ when $p_i\le p_j$.

Firstly, you should read the integer $n$ ($1\le n\le 2000$). After that, you can make no more than $4 \times 10^4$ queries. To make a query, output ``${?~l~r}$'' ($1 \leq l \leq r \leq n$) on a separate line, then you should read the response from standard input. To give your answer, print ``${!~p_1~p_2~\dots~p_n}$'' on a separate line. The output of the answer is \textbf{not} counted towards the limit of $4 \times 10^4$ queries. After that, your program should terminate. After printing a query, do not forget to output end of line and flush the output. To do this, use $\texttt{fflush(stdout)}$ or $\texttt{cout.flush()}$ in C++, $\texttt{System.out.flush()}$ in Java, $\texttt{flush(output)}$ in Pascal, or $\texttt{stdout.flush()}$ in Python. It is guaranteed that the permutation is fixed in advance.

3

0

0

1

? 1 2

? 1 3

? 2 3

! 2 3 1