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

長さ $n=30000$ の順列 $p$ がジャッジによって隠されています。あなたの課題は、この順列の最小値のインデックスを見つけることです。

ジャッジは非適応的です：順列はインタラクション開始前に選択され、その後変更されることはありません。

通常の比較クエリとは異なり、ジャッジは現在のクエリを直前のクエリとのみ比較します。より正確には、直前のクエリのインデックスが $i$ で、今 $j$ をクエリすると、ジャッジは $p_i$ と $p_j$ の比較結果を教えます。

最大で $q_{\max}=42000$ 回のクエリを行うことができます。

公式のジャッジデータは100個の独立したテストファイルから構成されます。あなたのプログラムは各ファイルに対して独立に実行されます。

インタラクション

インタラクションの最初に、あなたのプログラムは2つの整数 $$ n \quad q_{\max} $$ を読み込まなければなりません。

公式テストでは、$n=30000$, $q_{\max}=42000$ です。

クエリを行うには、次の形式で1行を出力します： $$ \text{? j} $$ ただし $1 \le j \le n$ です。

ジャッジは1文字で応答します：

• < : $p_i < p_j$ の場合（$i$ は直前のクエリのインデックス（存在する場合））
• = : 初めてのクエリの場合、または $p_i = p_j$ の場合
• > : $p_i > p_j$ の場合（$i$ は直前のクエリのインデックス（存在する場合））

$p$ は順列なので、最初のクエリ以降に = が返るのは、直前と同じインデックスをクエリした場合のみです。

ジャッジが -1 を返した場合、プログラムは直ちに終了しなければなりません。これは、プログラムがインタラクションプロトコルに違反したことを意味し、不正解 (Wrong Answer) となります。

最終的な解答を出力するには、次の形式で1行を出力します： $$ \text{! a} $$ ここで $a$ は最小値があると主張するインデックスです。解答を出力した後、プログラムは終了しなければなりません。最終解答はクエリとしてカウントされません。

プログラムが $q_{\max}$ 回を超えてクエリを行った場合、無効なインデックスをクエリした場合、無効なコマンドを出力した場合、または誤った最終解答を出力した場合、不正解 (Wrong Answer) となります。

クエリまたは解答を出力するたびに、出力をフラッシュしてください。例えば、C++ では endl や cout.flush() を使用できます。

注記

このサンプルはあくまでインタラクションの例であり、実際のテストデータには含まれません。(receiving ... output) のような行は、サンプル内でクエリとジャッジの応答を揃えるために使用されるプレースホルダです。実際のテストケースでは、ジャッジはこれらのプレースホルダ行を出力しません。参加者はそれらを読み取ったり出力したりしてはいけません。

この例のインタラクションでは、隠された順列は $p=(3,1,4,2)$ です。以下の箇条書きはサンプルに示されたインタラクションを説明しています。

• ジャッジは最初に $n=4$ とクエリ上限 $5$ を送信します。
• 最初のクエリ ? 1 は、直前のクエリインデックスがないため = を受け取ります。
• クエリ ? 2 は $p_1=3$ と $p_2=1$ を比較するため、ジャッジは > を返します。
• クエリ ? 4 は $p_2=1$ と $p_4=2$ を比較するため、ジャッジは < を返します。最小値はインデックス $2$ にあるので、! 2 が正解です。

ローカルインタラクションツール： 添付の attachments/local_interactive.py を使用すると、--perm 3,1,4,2 --limit 5 でこのローカル設定を再現できますが、これを通過しても公式のジャッジデータを通過することを保証するものではありません。