题目描述

题目译自 BalticOI 2023 Day1「Staring Contest」

盯人比赛是一种经典的冷静的较量，两个人一边盯着对方的眼睛看，一边保持一种平静的面部表情。比赛目标是保持目光对视的时间比对手长。当一方打破平静时，比赛就结束了，通常是移开视线、微笑、说话或傻笑。

作为全国盯人比赛的教练，你需要为即将到来的世界总决赛确定每名队员 $n$ 的冷静能力。第 $i$ 名运动员能保持目光对视的时间正好是 $a_i$ 秒，但这些值在开始时是未知的。例如，你可能有一支由 $n=3$ 成员组成的队伍：

当队员 $i$ 和 $j$ 比赛时，比赛持续的时间正好是 $\min(a_i, a_j)$ 秒，此时，实力较弱的选手会打破平静，双方都会在几分之一秒内开始傻笑。例如，如果 Anna 与 Esther 比赛，比赛将持续 $431$ 秒。重要的是，对于外部观察者来说，比赛的实际获胜者（在本例中为 Esther）是无法确定的，只有比赛的持续时间是可以测量的。

你的目标是利用尽可能少的盯人比赛来估计 $a_1,\ldots,a_n$。显然，最强运动员的实力永远无法确定，因此允许你低估其中一个 $a_i$。

交互过程

这是一道交互题。交互开始于你读入一行一个整数 $n$。然后你可以以 $\texttt{?}\ i\ j$ 的形式询问一个问题，其中 $1\le i,j\le n$ 且 $i\neq j$。询问的回答为一个整数：$\min(a_i,a_j)$ 的值。交互结束于你输出一行，首先输出一个 $\texttt{!}$，接着输出 $n$ 个由空格分隔的估计值 $b_1,\ldots,b_n$。这必须是你输出的最后一行。

特别提示：对于每行输出，你必须输出换行（\n），并刷新缓冲区。

如果对于除了一个被低估的之外的所有 $i$ 都满足 $b_i=a_i$，则你的提交是正确的。更精确地，我们要求对于所有 $1\le i\le n$ 满足 $b_i\le a_i$，且允许最多一个 $k$ 满足 $b_k\neq a_k$。

交互器是非适应性的，也就是说 $a_1,\ldots,a_n$ 的值在交互开始之前已经确定好了。

数据范围和计分

队员人数 $n$ 满足 $2\le n\le 1500$，每个队员的冷静能力满足 $1\le a_i\le 86\ 400$，并且它们互不相同。你可以最多询问 $3000$ 次。你输出的最后一行，即以 $\texttt{!}$ 开始的行不算在询问内。

你的提交将在一些子任务中进行测试，每个子任务都有一定的分数。每个子任务都包含一些测试用例。要获得子任务的分数，你需要解决子任务中的所有测试用例。你的最终得分将是单次提交的最高分。

对于第三个子任务，你的得分是子任务中所有测试用例得分的最小值。每组测试用例的得分取决于你使用的询问次数；询问次数越少越好：假设你使用了 $q$ 次询问。如果 $q\le n+25$，那么你会得到满分 $80$ 分。如果 $q>3000$，则你不得分。否则，你会得到 $118.2-12\cdot\ln(q-n)$ 分，四舍五入到最近的整数。例如，如果 $n=1500$ 且 $q=3000$，你会得 $30$ 分。

样例交互

样例交互使用上文中提到的例子展示了一种可能的交互过程。注意 Anna 和 Tony 的冷静能力被正确地确定了（Esther 的不可能被确定）。