P17038 [NWERC 2021] 解闷游戏 / Boredom Buster

译自 [Northwestern Europe Regional Contest (NWERC) 2021](http://2021.nwerc.eu) Problem B。 原题许可协议为 CC BY-SA。

你独自被困在一间小木屋里，外面正下着雨。你无聊得快疯了，唯一能打发时间的东西是一副 Memory 记忆牌。一个人玩 Memory 并不太有趣，但你设计了一个单人变体，它不仅需要好的记忆力，也需要策略。 游戏规则如下：你有一副洗乱的 $n$ 张牌，其中 $n$ 为偶数，每张牌上写有一个从 $1$ 到 $\frac{n}{2}$ 的数字。每个数字恰好出现两张牌。牌面朝下放在桌上，你的目标是确定每张牌上写着什么数字。 每一步，你拿起两张牌。在翻开它们之前，你会随机打乱这两张牌，使得你不知道哪张牌原本在哪里。然后你查看这两张牌。之后，在把它们放回原来的两个位置之前，你再次将它们牌面朝下随机打乱。这样一来，你知道这两个位置上的数字以及它们所在的位置，但不知道最后哪张牌落在哪个位置，甚至不知道最初哪张牌来自哪个位置。 你的任务是编写一个程序来赢下这个游戏。 ### 交互格式 这是一道交互题。你的程序会与一个 **交互器** 一起运行；交互器读取你程序的标准输出，并向你程序的标准输入写入内容。交互过程必须遵循以下协议： - 交互器首先发送一个整数 $n$（$2 \leq n \leq 10^5$，$n$ 为偶数）。只有在样例中，$n$ 才可能不等于 $10^5$。 - 之后，你的程序可以反复输出两个整数 $x$ 和 $y$（$1 \leq x,y \leq n$，$x \neq y$），并在前面加上 `?`。 - 交互器返回两个整数 $a$ 和 $b$（$1 \leq a,b \leq \frac{n}{2}$），表示查询之后要么第 $x$ 张牌为 $a$ 且第 $y$ 张牌为 $b$，要么第 $x$ 张牌为 $b$ 且第 $y$ 张牌为 $a$。 - 当你准备输出答案时，输出 `!`，后面跟着 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示 **输出时刻** 第 $i$ 张牌上的数字。 你最多可以使用 $92\,000$ 步。输出答案不计为一步。 交互器不是自适应的。牌的初始位置在任何交互发生前就已由交互器确定。当你进行一步操作时，交互器会在展示给你之前以及放回去之前，都分别将这两张牌均匀随机地打乱。初始牌面保证是 $1,1,2,2,\ldots,\frac{n}{2},\frac{n}{2}$ 的一个随机排列。 你的程序会在恰好 $100$ 个测试用例上运行，每个测试用例都有 $n=10^5$。 每次写入后请确保刷新输出缓冲区。题包中提供了一个测试工具，帮助你调试程序。

无

无

【数据规模与约定】 对于所有数据，$2 \leq n \leq 10^5$，$n$ 为偶数；正式测试中恰好有 $100$ 个测试用例，且每个测试用例 $n=10^5$。最多允许 $92\,000$ 步，输出答案不计入步数。