题目描述

给定一个长为 $n$ 的序列 $a$，定义回听操作如下：

定义一次回听操作为，任意选择一个 $x\in [1,n]$，然后进行任意次（可以是 $0$ 次）如下操作：

• $a_x \leftarrow \max\{a_x-1,0\}$，选择一个 $j\in[1,x)$，交换 $a_x,a_j$ 并令 $x \leftarrow j$。

定义 $b_i$ 为进行一次回听后 $a_i$ 的最小值。

注意此处回听操作不会实际影响序列 $a$ 的值。可以认为操作之后 $a$ 会恢复到操作之前的状态。

序列会进行 $m$ 次修改操作，每次给定 $l,r,v$，使 $a_l$ 到 $a_r$ 中的每个数增加 $v$。每次修改后你需要输出进行一次回听操作后本质不同的 $b_i$ 共有多少个（$b_i$ 与 $b_j$ 本质不同当且仅当 $b_i \ne b_j$）。

注意：修改操作间相互影响，回听操作间相互独立。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来 $m$ 行每行 $3$ 个整数，分别表示 $l,r,v$。

输出格式

共 $m$ 行，每行一个整数代表本质不同的 $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

提示

【操作解释】

对于序列 $\{3,8,2,4,7\}$，对它进行回听操作的过程如下：

若选择 $x=5$，进行 $3$ 次操作，选择的 $j$ 分别为 $4,2,1$，那么整个序列会这样变化：

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

【样例 $1$ 解释】

修改操作后序列 $a$ 变为 $\{ 2,3,3\}$。

当 $i=1$ 时，选择 $x=3$，进行 $2$ 次操作，$j$ 分别选择 $2,1$，得到 $b_i=a_3-1-1=1$。

当 $i=2$ 时，选择 $x=2$，进行 $1$ 次操作，选择 $j =1$，得到 $b_i=a_1=2$。

当 $i=3$ 时，选择 $x=3$，进行 $1$ 次操作，选择 $j =1$，得到 $b_i=a_1=2$。

综上，序列 $b$ 为 $\{ 1,2,2\}$，故答案为 $2$。

【数据范围】

本题采用捆绑测试。

• 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）：无特殊限制。

对于所有测试数据，保证 $1\le n,m\le 5\times10^5$，$1\le a_i,v\le 10^6$，$1\le l\le r\le n$。

本题输入输出量较大，建议使用较快的 IO 方式。