某外星行星的地表大部分是沙漠，因此很少下雨。生活在这颗行星上的植物都是仙人掌。由于降雨稀少，仙人掌进化出了相互协作以储存水分的方法。
该行星的一个区域是一个仅存在上下和左右方向的二维平面。在该区域中，有 $N$ 个仙人掌并排站立。所有仙人掌的宽度均为 1 米。仙人掌的高度可能各不相同。为了美化环境，假设只保留从第 $S$ 个仙人掌到第 $E$ 个仙人掌，此时降下了充足的雨水。因此，仙人掌上方可以蓄水的区域都积满了水。也就是说，水会像下图中那样积聚。在下图中，应认为箭头所示范围之外的仙人掌已不存在。
请编写一个程序，输入仙人掌的高度和保留的仙人掌范围，计算积水的总量（面积）。保留仙人掌的范围最多会给出 $Q$ 次。给出的范围总是应用于所有仙人掌都存在的初始状态。你需要实现以下函数：
void init( int H[] )：此函数仅在最开始调用一次。H是一个大小为 $N$ 的数组（vector），按顺序存储了从最左侧仙人掌开始的各仙人掌高度。$N$ 是仙人掌的数量。long long query( int S, int E )：当保留从第 $S$ 个仙人掌到第 $E$ 个仙人掌时，在降下充足雨水的情况下，返回积水的总量（面积）。($1 \le S \le E \le N$) 此函数最多被调用 $Q$ 次。所有调用都是独立的。也就是说，一次调用中仙人掌的消失与另一次调用无关。
实现细节
你需要提交一个名为 cactus.cpp 的文件。该文件中必须实现以下函数：
void init( int H[] )long long query( int S, int E )
这些函数必须按照上述说明进行操作。当然，你也可以在内部创建其他函数。提交的代码不得执行输入输出操作或访问其他文件。
样例
输入格式 1
10 3 1 3 2 5 1 4 6 2 1 3 2 8 2 4 7 9
输出格式 1
6 1 0
说明
init( {1, 3, 2, 5, 1, 4, 6, 2, 1, 3} )：初始调用。query( 2, 8 )：Query 调用，返回 6。query( 2, 4 )：Query 调用，返回 1。query( 7, 9 )：Query 调用，返回 0。
数据范围
- $1 \le N \le 500,000$
- $1 \le Q \le 500,000$
- 仙人掌高度在 $1$ 到 $10^9$ 之间
子任务
- 子任务 1 [13 分]：$1 \le N \le 5,000, 1 \le Q \le 5,000$
- 子任务 2 [12 分]：$1 \le N \le 5,000$
- 子任务 3 [22 分]：仙人掌高度不超过 $20$
- 子任务 4 [34 分]：$1 \le N \le 100,000, 1 \le Q \le 100,000$
- 子任务 5 [69 分]：除原有约束外无其他限制