問題文

ユキコダ社主催のプログラミングコンテストが開かれました。コンテストには $1, 2, \ldots , N$ の番号がついた $N$ 人が参加し、全員に $1$ 位から $N$ 位までの相異なる順位がつきました。

ユキコダ社採用担当のあなたは、$2$ 位の人をスカウトすることにしましたが、まだコンテストの結果を知らないので、参加者たちに質問することにしました。

参加者たちは皆ひねくれ者なので、次の形式の質問にしか答えてくれません。

• 人 $x$ と人 $y$ ($x\neq y$) ではどちらのほうが順位が上だったか？

この形式の質問を $334$ 回以下行って、$2$ 位の人の番号を特定してください。

入出力

最初に標準入力から参加者の人数 $N$ ($2\leq N\leq 300$) が以下のように与えられる。

$N$

続いて、あなたのプログラムは標準出力に以下の形式の質問クエリを $334$ 回まで行うことができる。

? $x\ y$

この出力は、人 $x$ と人 $y$ ではどちらのほうが順位が上だったか質問することを表す。$x$, $y$ は整数で、$1\leq x, y\leq N$, $x\neq y$ を満たさなければならない。

質問クエリを行うと、その回答が以下の形式で標準入力から与えられる。

$ans$

人 $x$ のほうが順位が上 (順位の数が小さい) ならば $ans=x$ であり、そうでないなら $ans=y$ である。

最後に、答えを以下の形式で出力しなければならない。

! $ans$

今までの質問クエリの内容から $2$ 位の人の番号をただ一つに決定できて、その番号が $ans$ に一致するとき、正解となる。

注意

• 出力のあと、標準出力をflushしなければならない。
• 質問クエリの後、その結果を必ず受け取ること。
• 答えを出力したあとはプログラムをすぐに終了しなければならない。
• テストケースの中には、質問クエリの回答がこれまでの質問クエリの内容により変化するものがあるが、回答がこれまでの質問クエリの内容に矛盾することはない。

サンプル

4
4
2
1

? 1 4
? 2 4
? 1 3
! 4

4
1
2
2

? 1 3
? 2 4
? 1 2
! 4