AT_arc192_c [ARC192C] Range Sums 2

**この問題はインタラクティブな問題です。** 正整数 $ N $ が与えられます。 すぬけくんは、 $ (1,2,\dots,N) $ を並び替えた正整数列 $ P=(P_1,P_2,\dots,P_N) $ と、長さ $ N $ の正整数列 $ A=(A_1,A_2,\dots,A_N) $ を隠し持っています。**ここで、 $ P_1 $ N $ 次に、あなたはすぬけくんに $ 2N $ 回以下クエリを送ることができます。**相異なる**正整数 $ s,t $ を指定してクエリを送るとき、以下のように出力してください。末尾に改行を入れることを忘れないでください。 > ? $ s $ $ t $ クエリを送ると、すぬけくんからの返答が以下の形式で標準入力から与えられます。 > $ X $ ここで、 $ X $ は整数で、 - $ X\ne -1 $ のとき $ \displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i $ の値が $ X $ であることを表します。 - $ X=-1 $ のとき、 $ s,t $ が制約を満たしていないか、クエリを送った回数が $ 2N $ 回を超えたことをします。 - このとき、プログラムはすでに不正解とみなされています。ただちにプログラムを終了してください。 $ P $ と $ A $ を特定することができたら、答えを以下の形式で出力してください。これはクエリの回数には計上されません。 > ! $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ **特に $ P_1

N/A

N/A

### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力をflushしてください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。** - 解答を出力したとき、または `-1` を標準入力から受け取ったとき、ただちにプログラムを終了してください。そうしなかった場合の判定結果は不定です。 - 余計な改行は不正なフォーマットの出力とみなされることに注意してください。 - **この問題のジャッジシステムは適応的ではありません。** つまり、 $ P $ と $ A $ はジャッジとの対話前に決定され、いかなるタイミングでも変更されることはありません。 ### 入出力例 $ N=6,P=(2,4,6,5,3,1),A=(1,9,2,25,2,9) $ のときの対話の一例を示します。 入力 出力 説明 `6` まず整数 $ N $ が標準入力から与えられます。 `? 1 2` $ s=1,t=2 $ としてすぬけくんにクエリを送ります。 `36` 出力は制約を満たしているので、 $ \displaystyle \sum_{i=\min(P_1,P_2)}^{\max(P_1,P_2)}A_i $ の値である $ 36 $ が与えられます。 `? 2 5` $ s=2,t=5 $ としてすぬけくんにクエリを送ります。 `27` 出力は制約を満たしているので、 $ \displaystyle \sum_{i=\min(P_2,P_5)}^{\max(P_2,P_5)}A_i $ の値である $ 27 $ が与えられます。 `! 2 4 6 5 3 1 1 9 2 25 2 9` $ P $ と $ A $ が特定できたことを報告します。この出力の後、ただちにプログラムを終了することで正解と判定されます。 これは対話の一例であることに注意してください。特に、ここまでのクエリとその返答で $ P $ と $ A $ を確実に特定できるとは限りません。 ### Constraints - $ 3\leq N\leq 5000 $ - $ 1\leq P_i\leq N $ $ (1\leq i\leq N) $ - $ P_i\ne P_j $ $ (i\ne j) $ - $ P_1