AT_bogosortcontest_div1_l Consecutive Pairs

これはインタラクティブな問題です。 tatesoto 君は、 $ (1, 2, \dots, N) $ の順列 $ P = (P_1, P_2, \ldots, P_N) $ を隠し持っています。 tatesoto 君からの情報により、 $ P $ において $ 1 $ は $ N $ より前に現れることがわかっています。 あなたは、tatesoto 君に対して以下の質問を行うことができます。 - $ 1 \le l \le r \le N $ を満たす整数 $ l, r $ を選ぶ。次の条件を満たす整数 $ x $ の個数 $ k $ を聞く。 - $ 1 \le x \lt N $ かつ、 $ x $ と $ x+1 $ の両方が $ (P_l, P_{l+1}, \ldots, P_r) $ に含まれる。 $ 12N $ 回以下の質問によって、tatesoto 君が隠し持っている順列 $ P $ を特定してください。 なお、tatesoto 君は常に正直で、隠し持っている順列 $ P $ をやりとりの途中で変えるようなことはしません。 ### Input & Output Format この問題はインタラクティブな問題です。 最初に $ N $ を標準入力から受け取ってください。 > $ N $ 次に、順列 $ P $ が特定できるまで質問を繰り返してください。 質問は、以下の形式で標準出力に出力してください。ここで、 $ l, r $ は $ 1 \le l \le r \le N $ を満たす整数です。 > ? $ l $ $ r $ これに対する応答は、次の形式で標準入力から与えられます。 > $ k $ ここで、 $ k $ は質問に対する答えで、次の条件を満たす整数 $ x $ の個数を表します。 - $ 1 \le x \lt N $ かつ、 $ x $ と $ x+1 $ の両方が $ P_l, P_{l+1}, \ldots, P_r $ に含まれる。 ただし、 $ l, r $ が制約をみたしていないか、質問の回数が $ 12N $ 回を超えた場合は $ k $ は `-1` となります。 ジャッジが `-1` を返した場合、プログラムはすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。 順列 $ P $ の要素を全て特定できたら、特定した $ P $ の要素を以下の形式で出力してください。その後、ただちにプログラムを終了してください。 > ! $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ なお、ジャッジは適応的 (adaptive) ではなく、 $ P = (P_1, P_2, \ldots ,P_N) $ はやりとりの前から固定されています。

N/A

N/A

### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。**そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。 - 解答を出力したら (または -1 を受け取ったら) ただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。 - 余計な改行は不正なフォーマットの出力とみなされることに注意してください。 ### 入出力例 入力 出力 説明 `4` $ N $ が与えられます。この例では、tatesoto 君は $ P=(2,3,1,4) $ を隠し持っています。 `? 1 2` $ l=1,r=2 $ として質問します。 `1` $ (P_1,P_2) = (2, 3) $ は $ x = 2 $ だけが条件を満たすため、 $ 1 $ が返されます。 `? 2 3` $ l=2,r=3 $ として質問します。 `0` $ (P_2,P_3) = (3, 1) $ には条件を満たす $ x $ が存在しないため、 $ 0 $ が返されます。 `? 3 4` $ l=3,r=4 $ として質問します。 `0` $ (P_3,P_4) = (1, 4) $ には条件を満たす $ x $ が存在しないため、 $ 0 $ が返されます。 `? 1 3` $ l=1,r=3 $ として質問します。 `2` $ (P_1,P_2,P_3) = (2, 3, 1) $ は $ x = 1, 2 $ が条件を満たすため、 $ 2 $ が返されます。 `? 2 4` $ l=2,r=4 $ として質問します。 `1` $ (P_2,P_3,P_4) = (3, 1, 4) $ は $ x = 3 $ だけが条件を満たすため、 $ 1 $ が返されます。 `! 2 3 1 4` 順列を $ P=(2,3,1,4) $ と特定し、出力してプログラムを終了します。なお、 $ P=(3,2,4,1) $ もここまでの質問に対する応答と矛盾しませんが、 $ P $ において $ N=4 $ が $ 1 $ より前に現れているので不適です。 ### Constraints - $ 2 \leq N \leq 2000 $ - $ 1 \leq P_i \leq N $ - $ P_i \neq P_j \ (i \neq j) $ - $ P_i = 1 $ かつ $ P_j = N $ を満たす $ (i, j) $ について、 $ i < j $ が成り立つ - 入力される数値はすべて整数