AT_arc179_c [ARC179C] Beware of Overflow

[problemUrl]: https://atcoder.jp/contests/arc179/tasks/arc179_c この問題は**インタラクティブな問題**（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です. 正整数 $ N $ が与えられます. ジャッジシステムは正整数 $ R $ および $ N $ 個の整数 $ A_1,A_2,\dots\ ,A_N $ を隠し持っています. ここで $ |A_i|\le\ R,\ \left|\displaystyle\sum_{i=1}^{N}A_i\right|\ \le\ R $ を満たすことが保証されます. 絶対値が $ R $ 以下の整数しか書き込むことができない黒板があり, はじめは何も書き込まれていません. ジャッジシステムは, 黒板に $ A_1,A_2,\ \dots\ ,A_N $ の値を **この順で** 書き込みました. あなたは, 黒板にただ $ 1 $ つの値 $ \displaystyle\sum_{i=1}^{N}A_i $ が書き込まれている状態にする必要があります. あなたは $ R $ および $ A_i $ の値を直接知ることはできませんが, その代わりにジャッジシステムに対して次のやり取りを $ 25000 $ 回まで行うことができます. 正整数 $ i $ について, $ i $ 番目に黒板に書き込まれた整数を $ X_i $ とします. 特に, $ i=1,2,\dots\ ,N $ について $ X_i=A_i $ です. $ 1 $ 回のやり取りでは, 相異なる正整数 $ i,j $ を指定し, 次のいずれかを選んで行います. - 足し算をしてもらう. ジャッジシステムは黒板から $ X_i,X_j $ を消し, 新たに $ X_i+X_j $ の値を黒板に書き込む. - $ |X_i+X_j|\le\ R $ を満たしていなくてはならない. - 大小比較をしてもらう. ジャッジシステムは $ X_i\lt\ X_j $ の真偽を答える. ただし, 各やり取りを始める時点で $ i,j $ 番目に黒板に書き込まれた整数がすでに黒板から消されていてはなりません. 適切にやり取りを行って, 全てのやり取りを終えた後に黒板にただ $ 1 $ つの値 $ \displaystyle\sum_{i=1}^{N}A_i $ が書き込まれている状態にしてください. $ R $ および $ A_i $ はプログラムとジャッジシステムの対話の開始前に決定されます. ### Input & Output Format この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です. 最初に, $ N $ を標準入力から受け取ってください. > $ N $ 次に, 黒板にただ $ 1 $ つの値 $ \displaystyle\sum_{i=1}^{N}A_i $ が書かれている状態になるまで, やり取りを繰り返してください. 足し算をしてもらうときは, 以下の形式で標準出力に出力してください. 末尾に改行を入れてください. ここで $ i,j $ は相異なる正整数です. > + $ i $ $ j $ これに対するジャッジシステムの応答は, 次の形式で標準入力から与えられます. > $ P $ ここで $ P $ は整数で, - $ P\geq\ N+1 $ の場合は, $ X_i+X_j $ の値が黒板に書き込まれ, それが $ P $ 番目に書き込まれたことを表します. - $ P=-1 $ の場合は, $ i,j $ が制約を満たしていないか, やり取りの回数が $ 25000 $ 回を超えたことを表します. 大小比較をしてもらうときは, 以下の形式で標準出力に出力してください. 末尾に改行を入れてください. ここで $ i,j $ は相異なる正整数です. > ? $ i $ $ j $ これに対するジャッジシステムの応答は, 次の形式で標準入力から与えられます. > $ Q $ ここで $ Q $ は整数で, - $ Q=1 $ の場合は, $ X_i\

N/A

N/A

### 制約 - $ 2\leq\ N\leq\ 1000 $ - $ 1\leq\ R\leq\ 10^9 $ - $ |A_i|\leq\ R $ - $ \left|\displaystyle\sum_{i=1}^{N}A_i\right|\ \le\ R $ - $ N,R,A_i $ は整数. ### 注意点 - **出力を行うたびに, 末尾に改行を入れて標準出力を flush してください. そうしなかった場合, ジャッジ結果が TLE となる可能性があります.** - 解答を出力したら（または `-1` を受け取ったら）ただちにプログラムを終了してください. そうしない場合, ジャッジ結果は不定です. - 余計な改行は不正なフォーマットの出力とみなされることに注意してください. ### 入出力例 $ N=3,R=10,A_1=-1,A_2=10,A_3=1 $ のときの対話の一例を示します. 入力出力説明`3`まず整数 $ N $ が与えられます。`? 1 2`大小比較をしてもらいます.`1`$ X_1\lt\ X_2\ (-1\lt\ 10) $ なのでジャッジシステムは $ 1 $ を返します. `+ 1 3`足し算をしてもらいます.`4`ジャッジシステムは $ X_1=-1,X_3=1 $ を黒板から消し, $ X_1+X_3=0 $ の値を黒板に書き込みました. $ 4 $ 番目の書き込みでした.`+ 2 4`足し算をしてもらいます.`5`ジャッジシステムは $ X_2=10,X_4=0 $ を黒板から消し, $ X_2+X_4=10 $ の値を黒板に書き込みました. $ 5 $ 番目の書き込みでした.`!`黒板にはただ $ 1 $ つの値 $ \displaystyle\sum_{i=1}^{N}A_i $ が書き込まれている状態になったので, そのことをジャッジシステムに報告します.