题目描述

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

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

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

举个例子：$[4,3,3,4]$ 的分割权值和为分成 $[4,3],[3,4]$ 两段，即为 $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$。

输出格式

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

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

2
2
0

4 3
2 0 2 1
4 4 1
2 2 3
1 3 2

2
1
3

数据范围与提示

对于所有子任务，有 $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$。