Maximum Partition Weight After Range Updates

You are given an array \(a\) of \(n\) integers. Then, you are given \(q\) update operations. Each update is described by three integers \(l, r, x\): add \(x\) to every element in the subarray \(a[l\ldots r]\) (1-indexed).

After each update, you need to partition the array into one or more contiguous segments. For any segment, its weight is defined as the difference between its maximum and minimum value. The weight of a partition of the entire array is the sum of the weights of all its segments. Your task is to compute the maximum possible partition weight (i.e. the maximum over all ways to partition the array) after each update.

Observation and Hint: It can be shown that the answer after an update is given by \[ \max\Bigl((a_n - a_1) + \sum_{i=1}^{n-1} \max(0, -(a_{i+1}-a_i)),\ (a_1 - a_n) + \sum_{i=1}^{n-1} \max(0, a_{i+1}-a_i)\Bigr). \]

Here, \(a_1\) and \(a_n\) denote the first and last elements of the array, respectively, and the summations are taken over the differences between consecutive elements.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \leq n, q)\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the initial array.

Each of the following \(q\) lines contains three integers \(l, r, x\) (1-indexed) meaning add \(x\) to every element in the subarray \(a[l\ldots r]\).

outputFormat

For each update operation, output one line containing the maximum partition weight of the updated array.

sample

3 2
1 3 5
1 3 2
2 2 -1

4
4