配点 : $400$ 点

問題文

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

ジャッジが $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 となる可能性があります。
• 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
• 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
• 文字列 $S$ はあなたとジャッジの対話の開始時に固定され、あなたが行った質問などに応じて変更されることはありません。

入出力例

以下は、$N = 7, S = 0010011$ の場合の入出力例です。

解答した $p = 5$ について、$1 \leq p \leq N-1$ かつ $S_p \neq S_{p+1}$ が成り立ちます。 よって、この後ただちにプログラムを終了することで、正解と判定されます。