AT_xmascon16_a Array Sum

[problemUrl]: https://atcoder.jp/contests/xmascon16noon/tasks/xmascon16_a うさぎ准备了一个长度为 $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: 高桥くんと木の直径](http://abc019.contest.atcoder.jp/tasks/abc019_4)）。 ### 输入输出示例 以 $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 翻译