某个外星球的表面大部分是沙漠，因此很少下雨。这个星球上所有的植物都是仙人掌。由于雨水极为稀少，仙人掌进化出了相互合作储存水的方法。

星球上的某个区域是只有上下、左右方向的二维平面。这个区域中有 $N$ 株仙人掌紧挨着排成一行。每株仙人掌的宽度都是 $1$ 米，高度可以不同。为了美化环境，只保留第 $S$ 株到第 $E$ 株仙人掌，之后下了足够多的雨，使仙人掌上方所有能蓄水的区域都积满了水。积水情况如下图所示。图中箭头所标范围之外的仙人掌应视为已被移除。

请编写程序，给定仙人掌的高度和保留下来的仙人掌范围，以面积计算积水量。最多会给出 $Q$ 个范围。每个范围都始终作用于所有仙人掌均存在的初始状态。

你需要实现以下函数。

• void init( int H[] )：只在最开始调用一次。$H$ 是一个大小为 $N$ 的数组（向量），按从左到右的顺序存放仙人掌的高度。$N$ 是仙人掌的数量。
• int 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 行：$N$、$Q$。
• 下一行：$N$ 个正整数，按从左到右的顺序表示仙人掌的高度。
• 接下来 $Q$ 行：两个正整数 $S,E$，表示只保留第 $S$ 株到第 $E$ 株仙人掌时下雨（$1 \le S \le E \le N$）。

提供的评测程序将你的 query() 函数返回的值逐行输出，每行一个。

数据范围

• $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 分)

• 除原有数据范围外，没有额外限制。

样例

输入格式 1

10 3
1 3 2 5 1 4 6 2 1 3
2 8
2 4
7 9

说明

对于上述输入，你的代码的执行过程示例如下。