#include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define lbound(v, x) (int)(lower_bound(all(v), x) - v.begin()) #define ubound(v, x) (int)(upper_bound(all(v), x) - v.begin()) #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define FOR1(a) for (int _ = 0; _ < (a); ++_) #define FOR2(i, a) for (int i = 0; i < (a); ++i) #define FOR3(i, a, b) for (int i = (a); i < (b); ++i) #define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_) #define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i) #define RFOR3(i, a, b) for (int i = (b)-1; i >= (a); --i) #define overload3(a, b, c, d, ...) d #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int>> r_pqi; typedef priority_queue<ll, vll, greater<ll>> r_pqll; typedef priority_queue<pii, vpii, greater<pii>> r_pqpii; typedef priority_queue<pll, vpll, greater<pll>> r_pqpll; struct Node { ll borders[2] = {0}; ll dp[2][2] = {0}; Node() {} Node(ll v) { borders[0] = borders[1] = v; dp[1][1] = abs(v); } Node comb(Node &other) { Node ret; ret.borders[0] = borders[0]; ret.borders[1] = other.borders[1]; REP(l, 2) { REP(a, 2) { REP(b, 2) { REP(r, 2) { if (a && b) { if ((borders[1] < 0) == (other.borders[0] < 0)) { ret.dp[l][r] = max(ret.dp[l][r], dp[l][a] + other.dp[b][r]); } } else { ret.dp[l][r] = max(ret.dp[l][r], dp[l][a] + other.dp[b][r]); } } } } } return ret; } void upd(ll v) { borders[0] += v; borders[1] += v; dp[1][1] = abs(borders[0]); } }; struct SegTree { Node val; int gL, gR, mid; SegTree *left, *right; SegTree(int l, int r, vector<Node> &nums) { gL = l; gR = r; mid = (gL + gR) / 2; if (l == r) { val = nums[l]; } else { left = new SegTree(l, mid, nums), right = new SegTree(mid + 1, r, nums); val = left->val.comb(right->val); } } void update(int idx, ll updval) { if (gL == gR) { val.upd(updval); } else { if (idx <= (gL + gR) / 2) { left->update(idx, updval); } else { right->update(idx, updval); } val = left->val.comb(right->val); } } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, Q; cin >> N >> Q; vector<Node> D(N - 1); int a; cin >> a; REP(i, N-1) { int b; cin >> b; D[i] = Node(b - a); swap(a, b); } SegTree sgt(0, N - 2, D); REP(Q) { int l; int r; ll x; cin >> l >> r >> x; l--, r--; if (l - 1 >= 0) { sgt.update(l - 1, x); } if (r < N - 1) { sgt.update(r, -x); } cout << sgt.val.dp[1][1] << '\n'; } }