Description

圣彼得堡是世界上最美丽的城市——除非下雨天。为了本题的设定，我们假设这里每天都在下雨。

圣彼得堡的一条街道形状特殊——它由 $n$ 个长度为 1 米的区块组成，其中第 $i$ 个区块距离地面的高度为 $a_i$ 米。街道深度为 1 米，前后两侧被极高的建筑物包围。因此下雨时，会有一定量的雨水因无法从街道最左端或最右端流出而积聚在街道上。 给定高度序列 $a_1, a_2, \ldots, a_n$，你需要计算街道上积聚的雨水量（单位：立方米）。

此外，市政建设公司的同事们将进行为期 $q$ 天的考察。在第 $i$ 天，他们会对从 $l_i$ 到 $r_i$ 的所有区块铺设沥青，使这些区块 $l_i, l_i+1, \ldots, r_i$ 的高度各增加 1 米。你需要分别计算在施工前，以及每天施工后的街道积水总量。

Input Format

第一行包含两个整数 $n$（区块数）和 $q$（施工天数）（$1 \le n, q \le 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示所有施工事件前的初始高度。 接下来 $q$ 行，每行包含两个整数 $l_i$, $r_i$（$1 \le l_i \le r_i \le n$），表示当天施工的区块范围。

Output Format

输出 $q+1$ 个整数，分别表示：所有施工前的积水量，以及每次施工后的积水量。

5 4
3 2 1 2 3
1 5
2 4
1 2
5 5

4
4
1
1
3

7 3
1 1000000000 1 1 1 1000000000 1
1 3
4 5
5 7

2999999997
2999999996
2999999994
2999999996

Hint

图示为第一个样例中街道的积水情况。

翻译由 DeepSeek V3 完成