Echo Operation and Unique Minimum Count

We are given a sequence (a = [a_1,a_2,\dots,a_n]) of length (n). We define an operation called the echo operation as follows:

Choose an index (x) (with (1\le x\le n)). Then, perform the following sub‐operation any number of times (possibly zero):

• Replace \(a_x\) with \(\max\{a_x-1,0\}\). Then, choose an index \(j\) with \(1 \le j < x\), swap \(a_x\) and \(a_j\), and update \(x\) to \(j\).

Define \(b_i\) to be the minimum value achievable at position \(i\) after performing exactly one echo operation (note that the echo operation is only simulated and does not permanently change \(a\)).

In other words, for each index \(i\) we have the following observation: to minimize the value at position \(i\), one may choose an index \(j\) with \(j\ge i\) and bring \(a_j\) to position \(i\) by performing exactly \(j-i\> swaps. In each swap the value is decreased by \(1\) (with a floor at \(0\)). Thus, one candidate for \(b_i\) is \(\max\{a_j-(j-i),0\}\) for every \(j\ge i\). Also, note that one may choose \(j=i\) (i.e. perform no swap), resulting in candidate \(a_i\). Therefore, we have:

\[ b_i = \min_{j=i}^{n}\;\max\{a_j-(j-i),0\}. \]

There are \(m\) modification operations on \(a\). Each modification is given as \(l, r, v\) and adds \(v\) to each \(a_i\) for \(l \le i \le r\) (modifications are cumulative). After each modification, you are to simulate one echo operation (which is independent for each modification) and output the number of essentially different values among \(b_1,b_2,\dots,b_n\) (two numbers are considered essentially different if they are not equal).

inputFormat

The input is given in the following format:

n m
a1 a2 ... an
l1 r1 v1
l2 r2 v2
...
lm rm vm

Here, (n) is the length of the sequence and (m) is the number of modification operations. The next line contains (n) integers representing the initial sequence (a). Each of the following (m) lines contains three integers (l, r, v) indicating that you should add (v) to each element of (a) from index (l) to (r) (inclusive).

outputFormat

For each modification operation, output a single line containing one integer — the number of distinct values in the sequence (b) after one echo operation is simulated on the current sequence.

sample

3 2
2 3 5
2 3 1
1 2 2

3
3

</p>