Description

这是一个交互式问题。

有一个隐藏的排列 $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$，否则为 $0$。

Input Format

首先，你需要读取整数 $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}$'' 在单独的一行上。答案的输出不计入 $4 \times 10^4$ 次查询的限制。

在打印查询后，不要忘记输出换行并刷新输出。为此，在 C++ 中使用 $\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$，在 Java 中使用 $\texttt{System.out.flush()}$，在 Pascal 中使用 $\texttt{flush(output)}$，在 Python 中使用 $\texttt{stdout.flush()}$。

保证排列是预先固定的。

3

0

0

1

? 1 2

? 1 3

? 2 3

! 2 3 1

Hint

题面翻译由 ChatGPT-4o 提供。