AT_xmascon16_a.Array Sum

うさぎ准备了一个长度为 $N$ 的整数序列 $a = \{a_0, a_1, ..., a_{N-1}\}$。

你可以向うさぎ提出如下类型的问题：

• 选择一组 $l, r\ (0 \leq l < r \leq N)$，使得 $r-l$ 是 $2$ 的幂（即 $1, 2, 4, 8, \ldots$），然后询问数列 $a$ 的区间 $[l, r)$ 的和，也就是 $(a_l + a_{l+1} + \ldots + a_{r-1})$。

请用尽可能少的询问次数，确定数列 $a$ 中所有数的总和。

1. 首先，输入一个整数 $N$，表示数列的长度。
2. 接下来，你的程序可以在不超过时间限制的情况下进行任意多次询问。
   1. 每次询问时，输出一行，内容为 ? 和两个整数 $l, r$，用空格分隔。
      • $l, r$ 必须满足题目中的条件。
   2. 随后，输入会给出数列 $a$ 的区间 $[l, r)$ 的和。
3. 最后，输出一行，内容为 ! 和数列 $a$ 的总和，用空格分隔。

请参考输入输出示例。

（本题无额外输出格式说明，详见输入格式。）

限制

• $1 \leq N \leq 10^5$。
• $0 \leq a_i \leq 10^4$。

评分

• 对于所有测试用例中，询问次数最多的那个用例，设其次数为 $x$，你的得分为 $900/\max(x,9)$ 的整数部分。
• 但如果有任何一个用例答案错误，则得分为 $0$。

注意事项

输出答案后，你的程序必须立即结束。如果没有立即结束，评测结果将不可预期。如果输出不正确，评测结果也不可预期（不一定是 WA）。

如果你的程序正确输出答案并结束，则视为正确。

注意，输出后必须刷新输出缓冲区，否则可能会因超时（TLE）而失败。

各语言的输入输出方法可参考 AtCoder 以往题目（链接: ABC 019 D: 高桥くんと木の直径）。

输入输出示例

以 $N=7, a = \{1,2,3,4,5,6,7\}$ 为例，给出输入输出示例。

输入	输出	说明
7		给出数列长度 $N$。
	? 0 1	询问区间 $[0,1)$ 的和。
1		回答为 $1$。
	? 0 4	询问区间 $[0,4)$ 的和。
10		回答为 $10$。
	? 1 3	询问区间 $[1,3)$ 的和。
5		回答为 $5$。
	? 3 7	询问区间 $[3,7)$ 的和。
22		回答为 $22$。
	! 28	输出答案 $28$。

由 ChatGPT 4.1 翻译