問題文

この問題は インタラクティブ な問題であり、 ジャッジは適応的(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 を当ててください。

制約

• 2\le N\le 2 \times 10^{5}
• N は整数
• P は (1,2,\dots,N-1) の順列

入出力

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

最初に、 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

この出力の後、ただちにプログラムを終了してください。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。
• 解答を出力したら (または -1 を受け取ったら) ただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
• 余計な改行は不正なフォーマットの出力とみなされることに注意してください。
• この問題のジャッジシステムは、適応的(adaptive)です。 つまり、ジャッジシステムは、任意のタイミングにおいて、整合性がとれる限り、 x として想定しているものを変更する可能性があります。詳しくは入出力例も参照してください。

入出力例

この入力では N=4,P=(2,1,3) であり、ジャッジシステムは最初 x=2 を想定しています。