题目描述

给定一个长度为 $n$ 的整数数组 $a[1..n]$，其中 $1 \le n \le 10,000$。 请你使用“分治+递归”的思路，构建区间和。

• 定义函数 build(l, r)：

  1. 如果 $l == r$，就输出一行 l r a[l]，表示区间 [l, l] 的和为 a[l]。

  2. 否则，先计算子区间的和：

     • mid = (l + r) / 2
     • 递归调用 build(l, mid) 与 build(mid+1, r)，
     • 然后 “向上合并” 得到子区间和的总和，即 $\text{sum} = \text{sum}_{[l,mid]} + \text{sum}_{[mid+1,r]}$，并输出一行 l r sum，表示根区间 [l, r] 的和。

请从 build(1, n) 开始，按照上述递归顺序，一行一个区间，输出“区间左右端点及其对应的区间和”。

输入格式

n
a_1 a_2 … a_n

• 第 1 行一个正整数 $n$，表示数组长度。（$1 \le n \le 10000$）
• 第 2 行 $n$ 个整数，用空格分隔，表示数组元素 $a_1, a_2, \dots, a_n$。 保证 $|a_i| \le 10^9$，并且在递归构建过程中任意区间和都不会超过有符号 64 位整数范围。

输出格式

按**“分治后序”**的顺序 — 也就是：

1. 先递归打印左子区间
2. 再递归打印右子区间
3. 最后输出当前区间的和

每行输出格式为：

l r sum

表示区间 [l, r] 的所有元素之和。

5
4 1 -2 3 7

1 1 4
2 2 1
1 2 5
3 3 -2
1 3 3
4 4 3
5 5 7
4 5 10
1 5 13