AT_kupc2024_l Long Street

この問題は **インタラクティブ** な問題であり、 **ジャッジは適応的(adaptive)** です。詳しくは注意点を参照してください。 $ 1 $ から $ N $ までの番号がついた $ N $ 点が、数直線上にこの順で並んでいます。 各 $ i $ $ (1\le i\le N-1) $ について、点 $ i $ と点 $ i+1 $ の距離は $ 2^{P_i} $ です。 $ N $ および $ P $ は入力で与えられます。 ジャッジシステムは $ 1\le x\le N $ を隠し持っています。 あなたは以下の質問を行うことができます。 - 整数 $ i $ $ (1\le i\le N) $ を選ぶ。 $ N $ 点のうち点 $ i $ が 点 $ x $ から何番目に近いかを聞く。 ただし、距離の順位は 1-indexed であり、例えば $ i=x $ の場合 1 番目と数える。 $ \lfloor\log_{2}{N}\rfloor $ 回以内の質問で $ x $ を当ててください。 ### Input & Output Format この問題はインタラクティブな問題です。 最初に、 $ N,P $ を標準入力から受け取ってください。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_{N-1} $ 次に、 $ x $ が特定できるまで質問を繰り返してください。 質問は以下の形式で標準出力に出力してください。 > ? $ i $ ここで、 $ i $ は $ 1 $ 以上 $ N $ 以下の整数である必要があります。 これに対する応答は、次の形式で標準入力から与えられます。 > $ r $ ここで、 $ r $ は質問に対する答えです。ただし、不正な質問を行った、あるいは質問の回数が $ \lfloor\log_{2}{N}\rfloor $ 回を超えた場合は $ r $ は `-1` となります。 ジャッジが `-1` を返した場合、提出はすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。 $ x $ が特定できたら、解答を以下の形式で出力してください。 > ! $ x $ この出力の後、ただちにプログラムを終了してください。

N/A

N/A

### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。**そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。 - 解答を出力したら (または `-1` を受け取ったら) ただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。 - 余計な改行は不正なフォーマットの出力とみなされることに注意してください。 - **この問題のジャッジシステムは、適応的(adaptive)です。** つまり、ジャッジシステムは、任意のタイミングにおいて、整合性がとれる限り、 $ x $ として想定しているものを変更する可能性があります。詳しくは入出力例も参照してください。 ### 入出力例 この入力では $ N=4,P=(2,1,3) $ であり、ジャッジシステムは最初 $ x=2 $ を想定しています。 入力 出力 説明 `4` `2 1 3` $ N,P $ が与えられます。 `? 4` $ i=4 $ として質問を行います。 `4` 質問の答えは $ 4 $ です。 `? 1` $ i=1 $ として質問を行います。 `3` 質問の答えは $ 3 $ です。 `! 2` $ x $ は $ 2 $ だと解答します。 確かにジャッジシステムが想定している $ x $ は $ 2 $ ですが、 $ 3 $ に変更しても整合性がとれます。 したがって、ジャッジシステムは不正解の判定を下すこともあります。 ### Constraints - $ 2\le N\le 2 \times 10^{5} $ - $ N $ は整数 - $ P $ は $ (1,2,\dots,N-1) $ の順列