問題文

この問題はインタラクティブ問題です。

整数 $N$ が与えられます。しょぼん君は $(0,1,\cdots, N-1)$ の順列 $P = (P_0, P_1, \cdots, P_{N-1})$ を持っています（添字が $0$ から始まることに注意してください）。

しょぼん君は恥ずかしがり屋なので、順列 $P$ をあなたに見せることはできません。その代わり、以下の質問に $\lfloor \frac{N}{2} \rfloor$ 回まで答えてくれます。ここで、実数 $x$ に対して $\lfloor x \rfloor$ は $x$ を超えない最大の整数とします。

• $0 \le x, y \lt N$ を満たす整数の組 $(x, y)$ を選び、$P_{z} = (P_x + P_y) \% N$ を満たす $z$ の値を聞く。ただし、整数 $s$ と正整数 $t$ に対して、$s \% t$ は $s$ を $t$ で割ったあまりとする。なお、$P_{z} = (P_x + P_y) \% N$ を満たす $z$ は必ず存在し、それがただ $1$ つであることが示される。

$P_k = 0$ を満たす $k$ を当ててください。なお、順列 $P$ はテストケースを通して固定されており、質問によって変わることはありません。

制約

• $3 \le N \le 1000$
• 入力はすべて整数

入出力

最初に、順列の長さ $N$ が与えられます。

$N$

その後、あなたは質問することができます。

質問は、以下の形式で標準出力に出力してください。

? $x$ $y$

質問に対する応答は、次の形式で標準入力から与られます。

$z$

ただし, $z$ は $P_z = (P_x + P_y) \% N$ を満たします。

$P_k = 0$ を満たす $k$ が分かったら、以下の形式で標準出力に出力してください。

! $k$

注意

• 出力のたびに必ず標準出力を flush してください。
• 不正な出力が行われた場合は不正解になりますが、ジャッジの結果は未定義であり、WA になるとは限りません。
• ! k を出力した後は、プログラムをすぐに終了させてください。

サンプル

以上のサンプルで、しょぼん君の持っている順列は $P = (1, 2, 0, 4, 3)$ でした。

たとえば $1$ 番目の質問 ? 3 1 については、$(P_3 + P_1) \% 5 = (4 + 2) \% 5 = 1$ であり、$P_0 = 1$ であるので、$0$ が返されます。