問題文

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

ジャッジが $0$ と $1$ のみからなる長さ $N$ の文字列 $S = S_1S_2\\ldots S_N$ を持っています。 文字列 $S$ は、$S_1 = 0$ および $S_N = 1$ を満たします。

あなたには $S$ の長さ $N$ が与えられますが、$S$ 自体は与えられません。 その代わり、あなたはジャッジに対して以下の質問を $20$ 回まで行うことができます。

• $1 \\leq i \\leq N$ を満たす整数 $i$ を選び、$S_i$ の値を尋ねる。

$1 \\leq p \\leq N-1$ かつ $S_p \\neq S_{p+1}$ を満たす整数 $p$ を $1$ 個出力してください。
なお、本問題の条件下でそのような整数 $p$ が必ず存在することが示せます。

制約

• $2 \\leq N \\leq 2 \\times 10^5$

入出力

最初に、文字列 $S$ の長さ $N$ を標準入力から受け取ってください。

$N$

次に、あなたはジャッジに対して問題文中の質問を $20$ 回まで繰り返すことができます。

質問は、以下の形式で標準出力に出力してください。 ここで、$i$ は $1 \\leq i \\leq N$ を満たす整数でなければなりません。

? $i$

これに対する応答として、$S_i$ の値が次の形式で標準入力から与えられます。

$S_i$

ここで、$S_i$ は $0$ または $1$ です。

問題文中の条件を満たす整数 $p$ を見つけたら、解答を以下の形式で出力してください。 その後、ただちにプログラムを終了してください。

! $p$

答えが複数ある場合、どれを出力しても正解とみなされます。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE