题目描述

译自 COCI 2020/2021 Contest #5 T5「Sjeckanie」

定义一个序列的权值为这个序列的最大值减去最小值。

定义一个序列的分割权值和为将这个序列分成若干段（段数可以为 $1$）后，所有段的权值和的最大值。

举个例子：$[4,3,3,4]$ 的分割权值和为分成 $[4,3],[3,4]$ 两段，即为 $(4-3)+(4-3) = 2$。

现有一个长为 $n$ 的序列 $a$，有 $q$ 次操作，每次操作将所有 $i \in [l,r]$，将 $a_i$ 加上 $x$（换言之，将 $a_l, a_{l+1}, \dots, a_r$ 分别加上 $x$），在每次操作之后，你需要求出这个序列的分割权值和。

输入格式

第一行为两个整数 $n, q$。

接下来一行 $n$ 个整数 $a_i$，表示初始序列 $a$。

接下来 $q$ 行，每行三个整数 $l, r, x$，表示这次的操作要将所有 $i \in [l,r]$，将 $a_i$ 加上 $x$。

输出格式

对于每次修改输出一行，表示您求出的这个序列的分割权值和。

样例 1

输入 4 3 1 2 3 4 1 2 1 1 1 2 2 3 1

text

输出 2 2 0

text

分割方式如下：

• 第一次修改后：$[2,3,3,4]$，分割为 $[2,3],[3,4]$，权值和为 $(3-2)+(4-3)=2$；
• 第二次修改后：$[4,3,3,4]$，分割为 $[4,3],[3,4]$，权值和为 $(4-3)+(4-3)=2$；
• 第三次修改后：$[4,4,4,4]$，所有元素相同，权值和为 $0$。

样例 2

输入 4 3 2 0 2 1 4 4 1 2 2 3 1 3 2

text

输出 2 1 3

text

数据范围与提示

对于所有子任务，有 $1 \le n,q \le 2 \times 10^5$，$-10^8 \le a_i,x \le 10^8$，$1 \le l \le r \le n$。