AT_arc179_c.[ARC179C] Beware of Overflow

本题为交互式问题（你的程序将与评测系统通过输入输出进行交互）。

给定一个正整数 $N$。

评测系统隐藏了一个正整数 $R$ 以及 $N$ 个整数 $A_1,A_2,\dots,A_N$。这里保证 $|A_i|\leq R$，且 $\left|\displaystyle\sum_{i=1}^{N}A_i\right|\leq R$。

有一个只能写入绝对值不超过 $R$ 的整数的黑板，初始时黑板上没有任何内容。

评测系统会依次将 $A_1,A_2,\dots,A_N$ 按顺序写到黑板上。你需要让黑板上最终只剩下一个值 $\displaystyle\sum_{i=1}^{N}A_i$。

你无法直接得知 $R$ 和 $A_i$ 的值，但你可以与评测系统进行最多 $25000$ 次的如下交互。

对于正整数 $i$，第 $i$ 次写入黑板的整数记为 $X_i$。特别地，对于 $i=1,2,\dots,N$，有 $X_i=A_i$。

每次交互，你可以指定两个不同的正整数 $i,j$，并选择以下操作之一：

• 让评测系统帮你做加法。评测系统会将黑板上的 $X_i,X_j$ 擦除，并新写入 $X_i+X_j$。
  • 要求 $|X_i+X_j|\leq R$。
• 让评测系统帮你做大小比较。评测系统会告诉你 $X_i<X_j$ 是否成立。

但每次交互开始时，$i,j$ 对应的整数必须仍在黑板上。

通过适当的交互操作，在所有交互结束后，使黑板上只剩下一个值 $\displaystyle\sum_{i=1}^{N}A_i$。

$R$ 和 $A_i$ 在程序与评测系统交互前就已确定。

本题为交互式问题（你的程序将与评测系统通过输入输出进行交互）。

首先，从标准输入读取 $N$。

$N$

接下来，重复进行交互，直到黑板上只剩下一个值 $\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<X_j$ 成立。
• $Q=0$ 表示 $X_i<X_j$ 不成立。
• $Q=-1$ 表示 $i,j$ 不满足约束，或交互次数超过 $25000$ 次。

无论是加法还是比较操作，只要评测系统的响应为 $-1$，你的程序就已被判为不正确。此时，请立即终止程序。

当黑板上只剩下一个值 $\displaystyle\sum_{i=1}^{N}A_i$ 时，请按以下格式向评测系统报告。此操作不计入交互次数。之后，请立即终止程序。

!

如果你的输出不符合上述任一格式，评测系统会返回 -1。

-1

此时也请立即终止程序。

无

约束条件

• $2\leq N\leq 1000$
• $1\leq R\leq 10^9$
• $|A_i|\leq R$
• $\left|\displaystyle\sum_{i=1}^{N}A_i\right|\leq R$
• $N,R,A_i$ 均为整数。

注意事项

• 每次输出后请务必刷新输出缓冲区，否则可能会导致评测结果为 TLE。
• 输出答案后（或收到 -1 后）请立即终止程序，否则评测结果不确定。
• 多余的换行会被视为输出格式错误，请注意。

输入输出样例

以 $N=3,R=10,A_1=-1,A_2=10,A_3=1$ 为例，交互过程如下：

输入输出说明
3 首先给出整数 $N$。
? 1 2 进行一次大小比较。
1 因为 $X_1 < X_2\ (-1 < 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$ 次写入。
! 黑板上只剩下 $\displaystyle\sum_{i=1}^{N}A_i$，向评测系统报告。

由 ChatGPT 4.1 翻译