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

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

此外，大都会建筑公司的同事将在 $q$ 天内进行施工，第 $i$ 天他们会在从 $l_i$ 到 $r_i$ 的所有区段上铺设沥青，从而使区段 $l_i, l_i+1, \dots, r_i$ 的高度各增加 1 米。你需要确定施工前以及每天施工后街道上积聚的雨水总量。

输入格式

第一行包含区段数量 $n$ 和施工事件数量 $q$ ($1 \le n, q \le 2 \cdot 10^5$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示所有事件发生前每个区段的高度。接下来的 $q$ 行，每行包含一对整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)，表示从 $l_i$ 到 $r_i$（包含两端）的施工工作。

输出格式

输出 $q+1$ 个整数，分别表示施工前以及每次更新后街道上的积聚水量。

样例

样例输入 1

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

样例输出 1

4
4
1
1
3

样例输入 2

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

样例输出 2

2999999997
2999999996
2999999994
2999999996

说明

下图展示了第一个样例中街道上积聚的雨水量。