Problem Description

Given a sequence $a$ of length $n$, define the playback operation as follows:

Define one playback operation as: choose any $x\in [1,n]$, and then perform the following operation any number of times (possibly $0$ times):

• $a_x \leftarrow \max\{a_x-1,0\}$, choose a $j\in[1,x)$, swap $a_x,a_j$, and set $x \leftarrow j$.

Let $b_i$ be the minimum possible value of $a_i$ after performing one playback operation.

Note that the playback operation does not actually affect the values of the sequence $a$. You may assume that after the operation, $a$ returns to the state before the operation.

The sequence will undergo $m$ modification operations. Each time, given $l,r,v$, increase every number from $a_l$ to $a_r$ by $v$. After each modification, you need to output how many essentially different $b_i$ there are after performing one playback operation (two values $b_i$ and $b_j$ are essentially different if and only if $b_i \ne b_j$).

Note: modification operations affect each other, while playback operations are independent of each other.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers, where the $i$-th integer represents $a_i$.

The next $m$ lines each contain $3$ integers, representing $l,r,v$.

Output Format

Output $m$ lines. Each line contains one integer, representing the number of essentially different $b_i$.

3 1
2 2 2
2 3 1

2

4 3
6 5 6 6
3 3 1
1 3 2
4 4 5

3
4
2

Hint

[Operation Explanation]

For the sequence $\{3,8,2,4,7\}$, the playback operation proceeds as follows:

If we choose $x=5$ and perform $3$ operations, with chosen $j$ being $4,2,1$ respectively, then the entire sequence changes as:

• $\{3,8,2,4,7\}$
• $\{3,8,2,6,4\}$
• $\{3,5,2,8,4\}$
• $\{4,3,2,8,4\}$

[Sample $1$ Explanation]

After the modification operation, the sequence $a$ becomes $\{ 2,3,3\}$.

When $i=1$, choose $x=3$, perform $2$ operations, and choose $j$ as $2,1$ respectively, obtaining $b_i=a_3-1-1=1$.

When $i=2$, choose $x=2$, perform $1$ operation, choose $j =1$, obtaining $b_i=a_1=2$.

When $i=3$, choose $x=3$, perform $1$ operation, choose $j =1$, obtaining $b_i=a_1=2$.

Therefore, the sequence $b$ is $\{ 1,2,2\}$, so the answer is $2$.

[Constraints]

This problem uses bundled testdata.

• Subtask 0 (10 pts): $1\le n,m \le 10$.
• Subtask 1 (15 pts): $1\le n,m \le 10^5$, $l\ge 2$, $a_1=1$, $\forall i\in[2,n],\,a_i>i$.
• Subtask 2 (15 pts): $1\le n,m \le 1000$.
• Subtask 3 (30 pts): $1\le n,m \le 10^5$.
• Subtask 4 (30 pts): no special constraints.

For all testdata, it is guaranteed that $1\le n,m\le 5\times10^5$, $1\le a_i,v\le 10^6$, $1\le l\le r\le n$.

The input/output size of this problem is large. It is recommended to use fast IO methods.

Translated by ChatGPT 5