题目描述

给定一个包含 $n$ 个整数的数组 $a$。接着进行 $q$ 次修改，每次给定整数 $l,r,x$。表示将 $[l,r]$ 内的所有元素加上 $x$。

规定一个区间的权值为该区间的最大值减去最小值。现要将 $a$ 数组分为若干个连续的区间。规定一个已被分为若干个区间的数组的权值为该数组所有区间的权值之和。求数组 $a$ 在每次修改后的所有分法中，数组权值的最大值。

输入格式

第一行输入整数 $n,q$，分别表示数组的长度和修改的次数。

第二行输入 $n$ 个整数 $a_i$。

接下来的 $q$ 行，每行输入整数 $l,r,x$，表示修改的信息。

输出格式

输出 $q$ 行，其中第 $i$ 行输出数组 $a$ 在第 $i$ 次修改后的所有分法中，数组权值的最大值。

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 解释

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$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$。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2020-2021 CONTEST #5 T5 Sjeckanje。