排列游戏

题目描述

这是一道交互题.

在你解决了一个又一个Orange提出的难题之后，你成功向Orange证明了自己的实力，你有能力留在CEIT工作。

现在，在你面试的最后一关，让我们来玩一个游戏吧！Orange会在心中想出一个 $n$ 的排列，这个排列在Orange想出之后就不会再发生改变。而你每次可以向Orange询问两个位置 $i$ 和 $j$，Orange将会告诉你 $a_i$ 和 $a_j$ 中的较小值。

你的任务是，在不超过 $8\times n$ 次的询问中，确定这个排列。当然，Orange为了降低难度，会适当的给你一些容错率（快感谢Orange），你最后得出的序列，只需要与Orange心中所想的排列的 汉明距离 不超过 $2$，就会被Orange认为是正确的。( tips:你最后得到的不一定需要是一个排列 )

排列：$n$ 的排列指的是一个长度为 $n$ 的整数序列，其中从 $1$ 到 $n$ 的每个整数都不重不漏地在序列中出现过一次。例如 $[1,3,4,2]$，是一个合法的 $4$ 的排列，而 $[2, 3]$ 不是一个合法的 $2$ 的排列，因为 $1$ 并没有出现过，且出现了 $1 \sim 2$ 范围之外的数 $3$。

汉明距离：汉明距离指的是对于两个等长的序列，他们的汉明距离就是通过替换某个位置的元素，将其中一个序列变成另一个序列的最小替换次数。例如：序列 $[\underline 1,4,3,\underline 2,5]$ 与 序列 $[4,4,3,3,5]$的汉明距离为 $2$，需要替换的位置如下划线所示。

交互形式

本题的交互支持以下两种形式：

• $?$ $i \ j$ - 表示向Orange提出你的询问位置，你将会得到一个整数 $p$，表示Orange对当前猜测的回答。其中 $p$ 满足:

• $!$ $a_1 \ a_2 \ a_3 \ \cdots \ a_n$ - 表示向Orange报告你的答案。

交互说明

1. 在交互开始前，你将会得到一个输入，为整数 $n$，表示你需要猜测的排列长度。随后，在交互开始时，您应提出一个问题。
2. 本题的交互是非实时的，答案为预先确定的，且不会发生改变。
3. 要进行查询，请输出一行格式为 ? i j 的内容。我们会向您的程序输入一个整数，表示本次查询的结果。
4. 当你确定好你的答案时，请使用输出一行格式为 ! a1 a2 a3 ... an 的内容，表示向Orange提交你的答案。提交答案不算作查询次数的一部分，请注意，你应该在回答答案后立刻终止您的程序。
5. 如果你的程序长时间没有应答（可能是你关闭了cin以及cout的同步流），或者询问了非法的数据或者提交了错误的答案以及询问次数超过 $8 \times n$ 次，程序会返回答案错误 或者 运行错误。
6. 输出查询后，不要忘记输出行尾并刷新输出。否则，您可能会收到超过闲置限制的判定。为此，请使用：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()；
• $\cdots$

特别提醒! 在回答交互性问题的时候，请不用关闭cin以及cout的同步流，避免交互程序无法收到您的交互请求。同时，如果你使用endl作为刷新缓冲区语句，请不用使用#define endl \n。

输入格式

在交互开始前

输入仅包含一行，包含一个整数 $n$，表示排列长度。

在交互过程中

输入一个整数 $p$，表示对于你查询的回答。

数据范围

$n \le 10^4$ $1 \le p \le n$

输出格式

在交互过程中

您的程序支持如下两种交互方式：

• 询问：请输出出形如? i j格式的询问指令。
• 提交答案：请输出形如! a1 a2 a3 ... an格式的指令来报告答案。

范围限制

对于每次询问，你应该保证 $1 \le i, j \le n$。 对于提交答案，你应该保证 $a_i$ 在 int 能表示的整数范围内。

样例 #1

样例输入 #1

1

样例输出 #1

! 1

提示

样例解释1

对于长度为 $1$ 的排列，仅存在一种排列为 $[1]$，因此答案是唯一确定的。

样例解释2

对于长度为 $2$ 的排列，其存在两种情况 $[1,2]$ 和 $[2,1]$，而他们与序列 $[2,2]$ 的汉明距离均不超过 $2$，因此答案 $[2,2]$ 会被认为是正确的。