#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i = a; i <= b; i++) #define FOD(i,a,b) for(int i = a; i >= b; i--) #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define lcm(a,b) (a*b)/__gcd(a,b) #define ii pair<int,int> #define iii pair<int,pair<int,int>> #define iv pair<pair<int,int>,pair<int,int>> #define sq(a) (a) * (a) const int inf = 1e9; const ll INF = 1e18; const int mod = 1e9 + 7; const int N = 2e5 + 5; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; const int dxx[] = {-1,-1,0,1,1,1,0,-1}; const int dyy[] = {0,1,1,1,0,-1,-1,-1}; int n, q; ll a[N], d[N]; struct Node { ll val[2], dp[2][2]; Node(int _val = 0) { val[0] = val[1] = _val; dp[0][0] = dp[0][1] = dp[1][0] = 0; dp[1][1] = abs(_val); } void up(int _val) { val[0] += _val; val[1] += _val; dp[1][1] = abs(val[0]); } }; struct Smt { Node seg[4 * N]; Node combine(Node a, Node b) { Node ret; ret.val[0] = a.val[0]; ret.val[1] = b.val[1]; FOR(l, 0, 1) { FOR(r, 0, 1) { FOR(u, 0, 1) { FOR(v, 0, 1) { if(u == v && u == 1) { if((a.val[1] < 0) == (b.val[0] < 0)) { ret.dp[l][r] = max(ret.dp[l][r], a.dp[l][u] + b.dp[v][r]); } } else { ret.dp[l][r] = max(ret.dp[l][r], a.dp[l][u] + b.dp[v][r]); } } } } } return ret; } void build(int id, int l, int r) { if(l > r) return; if(l == r) { seg[id] = Node(d[l]); return; } int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); seg[id] = combine(seg[id << 1], seg[id << 1 | 1]); } void up(int id, int l, int r, int pos, int val) { if(pos < l || pos > r) return; if(l == r) { seg[id].up(val); return; } int mid = l + r >> 1; up(id << 1, l, mid, pos, val); up(id << 1 | 1, mid + 1, r, pos, val); seg[id] = combine(seg[id << 1], seg[id << 1 | 1]); } }; Smt seg; void Solve() { // FOR(i, 1, n - 1) { // cout << d[i] << ' '; // } // cout << '\n'; seg.build(1, 1, n - 1); FOR(i, 1, q) { int l, r, x; cin >> l >> r >> x; if(l > 1) seg.up(1, 1, n - 1, l - 1, x); if(r < n) seg.up(1, 1, n - 1, r, -x); cout << seg.seg[1].dp[1][1] << '\n'; } } signed main() { // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int test = 1; // cin >> test; while(test--) { cin >> n >> q; FOR(i, 1, n) { cin >> a[i]; if(i > 1) { d[i - 1] = a[i] - a[i - 1]; } } Solve(); } } /* 1 2 3 2 1 5 + 3 1 5 6 5 1 a2 - a1 1 1 -1 -1 */