#include <bits/stdc++.h> using namespace std; using ll = long long; ll base = 1; struct node{ ll cost, len, fi, fifi, la, lala; }; struct Segment_tree{ vector<node> tree; vector<ll> lazy; void init(vector<ll> a, ll n){ while(base < n){ base *= 2; } tree.resize(2*base); lazy.resize(2*base); for(ll i = 0; i < base; i++){ tree[i+base].cost = 0; tree[i+base].len = 1; tree[i+base].fi = a[min(n-1, i)]; tree[i+base].la = a[min(n-1, i)]; } for(int i = base-1; i > 0; i--){ merge(i); } } void merge(ll id){ ll a = 2*id; ll b = 2*id+1; if(tree[a].len == 1){ tree[id].cost = abs(tree[a].fi - tree[b].fi); tree[id].len = 2; tree[id].fi = tree[a].fi; tree[id].fifi = tree[b].fi; tree[id].la = tree[b].fi; tree[id].lala = tree[a].fi; } else{ bool increasing1 = false, increasing2 = false, shift = false; if(tree[a].lala <= tree[a].la) increasing1 = true; if(tree[b].fi <= tree[b].fifi) increasing2 = true; if(tree[a].la <= tree[b].fi) shift = true; if(increasing1 && shift && increasing2){ tree[id].cost = tree[a].cost + tree[b].cost + (tree[b].fi-tree[a].la); } else if(increasing1 && !shift && increasing2){ tree[id].cost = max(tree[a].cost+tree[b].cost, tree[a].cost - (tree[a].la-tree[a].lala) + (tree[a].la-tree[b].fi) - (tree[b].fifi-tree[b].fi) + tree[b].cost); } else if(increasing1 && shift && !increasing2){ tree[id].cost = max(tree[a].cost+tree[b].cost, tree[a].cost + (tree[b].fi-tree[a].la) - (tree[b].fi-tree[b].fifi) + tree[b].cost); } else if(increasing1 && !shift && !increasing2){ tree[id].cost = max(tree[a].cost+tree[b].cost, tree[a].cost - (tree[a].la-tree[a].lala) + (tree[a].la-tree[b].fi) + tree[b].cost); } else if(!increasing1 && !shift && !increasing2){ tree[id].cost = tree[a].cost + tree[b].cost + (tree[a].la-tree[b].fi); } else if(!increasing1 && shift && !increasing2){ tree[id].cost = max(tree[a].cost+tree[b].cost, tree[a].cost - (tree[a].lala-tree[a].la) + (tree[b].fi-tree[a].la) - (tree[b].fi-tree[b].fifi) + tree[b].cost); } else if(!increasing1 && !shift && increasing2){ tree[id].cost = max(tree[a].cost+tree[b].cost, tree[a].cost + (tree[a].la-tree[b].fi) - (tree[b].fifi-tree[b].fi) + tree[b].cost); } else if(!increasing1 && shift && increasing2){ tree[id].cost = max(tree[a].cost+tree[b].cost, tree[a].cost - (tree[a].lala-tree[a].la) + (tree[b].fi-tree[a].la) + tree[b].cost); } tree[id].len = tree[a].len + tree[b].len; tree[id].fi = tree[a].fi; tree[id].fifi = tree[a].fifi; tree[id].la = tree[b].la; tree[id].lala = tree[b].lala; } } void push(ll id){ if(id >= base || lazy[id] == 0){ return; } lazy[2*id] += lazy[id]; lazy[2*id+1] += lazy[id]; tree[2*id].fi += lazy[id]; tree[2*id].fifi += lazy[id]; tree[2*id].la += lazy[id]; tree[2*id].lala += lazy[id]; tree[2*id+1].fi += lazy[id]; tree[2*id+1].fifi += lazy[id]; tree[2*id+1].la += lazy[id]; tree[2*id+1].lala += lazy[id]; lazy[id] = 0; } void add(ll id, pair<ll, ll> query, pair<ll, ll> range, ll x){ push(id); if(range.first > query.second || range.second < query.first){ return; } if(range.first >= query.first && range.second <= query.second){ lazy[id] += x; tree[id].fi += x; tree[id].fifi += x; tree[id].la += x; tree[id].lala += x; return; } ll mid = (range.first + range.second)/2; add(2*id, query, {range.first, mid}, x); add(2*id+1, query, {mid+1, range.second}, x); merge(id); } ll get(){ return tree[1].cost; } }; Segment_tree tree; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll n, q; cin >> n >> q; vector<ll> a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } tree.init(a, n); while(q--){ ll l, r, x; cin >> l >> r >> x; l--; r--; if(r == n-1) r = base-1; tree.add(1, {l, r}, {0, base-1}, x); cout << tree.get() << '\n'; } }