配点 : $700$ 点

問題文

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$ を全て求めてください。

制約

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

入出力

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

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

ジャッジ

• 出力を行うたびに、末尾に改行を入れて標準出力を flush せよ。そうしなかった場合、ジャッジ結果が TLE となる可能性がある。
• 答えを出力したら(または -1 を受け取ったら)直ちにプログラムを正常終了せよ。そうしなかった場合、ジャッジ結果は不定である。
• 余計な改行は不正なフォーマットの出力とみなされることに注意せよ。

入出力例

以下は、$N = 4,P=(3,1,2,4)$ の場合の入出力例です。