题目描述

PCT 君有一个 $(1,2,\dots,N)$ 的排列 $(P_1,P_2,\dots,P_N)$。你只知道 $N$ 的值。

你可以向 PCT 君最多询问 $25000$ 次以下的问题：

• 指定满足 $1\le i,j,k\le N$ 的整数三元组 $(i,j,k)$，询问 $P_i+P_j>P_k$ 是否成立。

请你求出 $P_1,P_2,\dots,P_N$ 的全部值。

输入格式

本题为交互题（你的程序需要与评测程序通过输入输出进行交互）。

首先，你的程序会从标准输入读入排列的长度 $N$。

$N$

之后，你可以进行提问。每次提问需要按如下格式输出到标准输出（末尾需换行）：

? $i$ $j$ $k$

如果提问合法，将会从标准输入读入该问题的答案 $ans$。

$ans$

其中，$ans$ 为 Yes 或 No。

如果你的提问格式有误，或者提问次数超过规定次数，标准输入会返回 -1。

-1

此时，评测程序已判定你的提交为不正确，并会立即结束交互。你的程序也应当立即退出。

当你确定 $P_1,P_2,\dots,P_N$ 的全部值后，请按如下格式输出答案（末尾需换行）：

! $P_1$ $P_2$ $\dots$ $P_N$

输出格式

无。

说明/提示

限制

• $1\le N\le 2000$
• $P$ 在程序与评测程序开始交互前已确定。

评测说明

• 每次输出后请务必刷新输出缓冲区，否则可能会因 TLE 被判为不正确。
• 输出答案（或收到 -1）后请立即正常退出程序，否则评测结果不确定。
• 多余的换行会被视为输出格式错误。

输入输出样例

以下为 $N=4,P=(3,1,2,4)$ 时的交互示例。

输入	输出	说明
4		$N$ 被给出。
	? 1 2 3	第 1 次提问，询问 $P_1+P_2>P_3$ 是否成立。
Yes		$P_1+P_2=4,P_3=2$，因此返回 Yes。
	? 2 3 3	第 2 次提问，询问 $P_2+P_3>P_3$ 是否成立。
Yes		$P_2+P_3=3,P_3=2$，因此返回 Yes。
	? 2 3 4	第 3 次提问，询问 $P_2+P_3>P_4$ 是否成立。
No		$P_2+P_3=3,P_4=4$，因此返回 No。
	! 3 1 2 4	输出 $P_1,P_2,P_3,P_4$。实际排列为 $(3,1,2,4)$，因此 AC。

由 ChatGPT 4.1 翻译