P12263 "STA - R9" Playback.

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.**

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 $m$ lines. Each line contains one integer, representing the number of essentially different $b_i$.

**[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