题目描述

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)$ を $1$ 個指定し、$P_i\ +\ P_j\ >\ P_k$ かどうかを聞く。

$P_1,P_2,\dots,P_N$ を全て求めてください。

Input & Output Format

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）である。

まず、あなたのプログラムに標準入力から順列の長さ $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$

题目大意

有一个隐藏的长度为 $n$ 的排列 $P$。

你可以询问交互库 ? i j k，交互库会判断 $P_i + P_j > P_k$ 是否为真命题，如果是则回答 Yes，否则回答 No。你需要在至多 $25000$ 次询问内找出该排列。

交互库不自适应，即排列 $P$ 是一开始就确定的。

$1 \leqslant n \leqslant 2000$。

提示

制約

• $1\ \le\ N\ \le\ 2000$
• $P$ はプログラムとジャッジの対話の開始前に決定される。

ジャッジ

• 出力を行うたびに、末尾に改行を入れて標準出力を flush せよ。そうしなかった場合、ジャッジ結果が 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 $ を出力します。実際に、$ P=(3,1,2,4) $ であるため、AC となります。