题目描述

这是一道交互题。

江月诗写下了一个长度为 $n$ 的排列 $a_{1},a_{2},\ldots,a_{n}$，随后隐藏了其中的所有数字。你只知道排列的长度 $n$，需要通过询问还原这个排列。

长度为 $n$ 的排列是指由 $1,2,\ldots,n$ 这 $n$ 个整数组成的数组，其中每个整数恰好出现一次。例如，$[3,1,4,2]$ 是一个长度为 $4$ 的排列，而 $[1,2,2,4]$ 不是。

每次询问，你可以选择两个不同的位置 $i$ 和 $j$，江月诗会告诉你这两个位置上的数之和，即 $a_{i}+a_{j}$。

你需要在至多 $n$ 次询问内，确定并输出整个排列。

隐藏排列在交互开始前已经确定，在整个交互过程中不会发生改变。

输入格式

每个测试点仅包含一组数据。

交互开始时，首先读入一个整数 $n$（$3 \le n \le 10^{4}$），表示隐藏排列的长度。

此后的输入为交互程序对你的询问给出的回答。隐藏排列不会直接提供给你的程序。

输出格式

你的程序需要通过标准输入和标准输出与交互程序通信。

进行一次询问时，输出一行，格式如下：

$$\texttt{?}\ i\ j$$

其中 $1 \le i,j \le n$ 且 $i \ne j$，各部分之间用空格分隔。

输出询问并刷新输出缓冲区后，读入一个整数 $s$，表示此次询问的回答：

$$s=a_{i}+a_{j}.$$

对于合法询问，返回值满足 $3 \le s \le 2n-1$。

你至多可以进行 $n$ 次询问。允许重复询问相同的一对位置，但每次询问都会计入询问次数。

确定整个排列后，输出一行，格式如下：

$$\texttt{!}\ a_{1}\ a_{2}\ \ldots\ a_{n}$$

其中 $a_{1},a_{2},\ldots,a_{n}$ 必须按照隐藏排列中的位置顺序给出，各部分之间用空格分隔。

输出最终答案不计入询问次数。输出并刷新最终答案后，你的程序应立即正常结束，无需读取额外反馈。

每次输出询问或最终答案后，都必须输出换行符并刷新输出缓冲区，否则可能得到 Idleness Limit Exceeded 的评测结果。

可以使用以下方式刷新输出缓冲区：

• C++：cout.flush() 或 fflush(stdout)。

• Python：sys.stdout.flush()。

• Java：System.out.flush()。

如果询问不合法，或者询问次数超过 $n$，交互程序将返回 $-1$，你的程序将被判定为 Wrong Answer。在任何时候读到 $-1$，都必须立即终止程序，否则可能得到其他评测结果。

4
6
3
5
5

? 1 2
? 1 3
? 2 3
? 1 4
! 2 4 1 3

样例解释

在样例中，隐藏排列为 $a=[2,4,1,3]$。交互程序首先给出排列长度 $n=4$，随后按照以下过程进行交互：

• 选手询问 ? 1 2，交互程序返回 $6$，因为 $a_{1}+a_{2}=2+4=6$。

• 选手询问 ? 1 3，交互程序返回 $3$，因为 $a_{1}+a_{3}=2+1=3$。

• 选手询问 ? 2 3，交互程序返回 $5$，因为 $a_{2}+a_{3}=4+1=5$。

• 选手询问 ? 1 4，交互程序返回 $5$，因为 $a_{1}+a_{4}=2+3=5$。

最后，选手输出 ! 2 4 1 3，正确还原了隐藏排列。

本次交互共进行了 $4$ 次询问，未超过 $n=4$ 次的限制。输出最终答案不计入询问次数。