题目描述

译自 JOISC 2018 Day2 T3「最悪の記者 3 / Worst Reporter 3」

在 IOI 2018 的入场仪式上，$N$ 位选手站成一排进入会场。我们不妨用数轴上的点来表示选手的位置。

旗手站在排头。开始时（时刻 $0$），旗手的位置为 $0$，$i$ 号选手的位置为 $-i$。旗手与选手们的移动方向均为数轴的正半轴。

我们用 $D_i$ 来描述 $i$ 号选手的缓慢程度。在每一时刻，旗手会向前走 $1$ 单位距离，$1\sim N$ 号选手依次检查他与前面的人的距离。

• 若距离 $\le D_i$，$i$ 号选手不移动；
• 若距离 $\ge D_i+1$，则 $i$ 号选手会立即向前走，走到距前者的后方 $1$ 单位距离的位置。

有 $Q$ 组查询，第 $j$ 组查询包含三个整数 $L_j, R_j, T_j$，试求：在时刻 $T_j$，有多少个人位于 $L_j$ 到 $R_j$ 之间（含端点）。

输入格式

第一行有两个整数 $N,Q$。
接下来 $N$ 行，每行一个整数 $D_i$。
接下来 $Q$ 行，每行三个整数 $T_j, L_j, R_j$。

输出格式

输出 $Q$ 行，第 $j$ 行有一个整数，表示第 $j$ 组查询的结果。

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

0
1
1
2
1
2

开始：

时刻 1：

时刻 2：

时刻 3：

时刻 4：

时刻 5：

时刻 6：

```input2 4 2 1 1 1 1 2 1 4 1 3 6 ``` ```output2 2 0 ``` ```input3 6 6 11 36 28 80 98 66 36 29 33 190 171 210 18 20 100 1000 900 1100 92 87 99 200 100 300 ``` ```output3 1 6 0 5 2 7 ``` ## 数据范围与提示

对于所有测试数据，$1\le N,Q\le 5\times 10^5,$ $1\le D_j, T_j\le 10^9,$ $1\le L_j\le R_j\le 10^9$。

子任务编号	分值	特殊限制
1	7	$D_i=1$
2	12	$N,Q\le 1000,$ $T_j,L_j,R_j\le 1000$
3	81	无特殊限制