题目描述

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

ジャッジが $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$ が必ず存在することが示せます。

Input & Output Format

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

$N$

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

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

? $i$

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

$S_i$

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

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

! $p$

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

题目大意

简述题意

• 交互库内有一个长度为 $n$ 的 $01$ 串 $S=S_1S_2S_3\ldots S_n$，其中 $S_1=0$，$S_n=1$。

• 最多询问交互库 $20$ 个问题，每次询问一个数 $x$，交互库返回 $S_x$ 的值。

• 目标寻找到一个数 $id$ ，使得 $S_{id}\neq S_{id+1}$。

• $1\leq n \leq 2e5$。

交互格式

具体地，交互库会先给出一个数 $n$。

若询问交互库 $S_x$ 的值，应当以 $\verb|? x|$ 的格式进行询问，交互库会给出 $S_x$ 的值。

若给出答案 $id$，应当以 $\verb|! id|$ 的格式给出答案，若 $S_{id}\neq S_{id+1}$ 则获得该测试点分数。你不应该在此之后输出任何字符。

Translated by yujinning。

提示

制約

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

注意点

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

入出力例

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

入力 出力 説明     `7`  $ N $ が与えられます。    `? 1` $ S_1 $ が何かをジャッジに質問します。     `0`  質問に対する答えとして $ S_1\ =\ 0 $ がジャッジから返されます。    `? 6` $ S_6 $ が何かをジャッジに質問します。     `1`  質問に対する答えとして $ S_6\ =\ 1 $ がジャッジから返されます。    `? 5` $ S_5 $ が何かをジャッジに質問します。     `0`  質問に対する答えとして $ S_5\ =\ 0 $ がジャッジから返されます。    `! 5` 問題文中の条件を満たす整数 $ p $ として、$ p\ =\ 5 $ を解答します。    解答した $ p\ =\ 5 $ について、$ 1\ \leq\ p\ \leq\ N-1 $ かつ $ S_p\ \neq\ S_{p+1} $ が成り立ちます。 よって、この後ただちにプログラムを終了することで、正解と判定されます。