题目描述

在 IOI 2018 的开幕式上，$N$ 名参赛者排成一列，该列由一条数轴表示。所有参赛者面向数轴的正方向前进。在时间 $0$ 时，第 $i$ 名参赛者（$1 \le i \le N$，从前向后计数）站在坐标 $-i$ 处。此外，旗手 IOI-chan 站在坐标 $0$ 处。

每名参赛者都有一个称为 迟滞值 的参数。第 $i$ 名参赛者的 迟滞值 为 $D_i$。参赛者遵循以下规则：

• 如果第 $i$ 名参赛者与他或她正前方的人（参赛者或 IOI-chan）之间的距离大于或等于 $D_i + 1$，则第 $i$ 名参赛者会移动到距离该人 $1$ 的位置。否则，第 $i$ 名参赛者不移动。

IOI-chan 每单位时间沿数轴正方向移动距离 $1$。每当上述条件满足时，参赛者会立即移动。

你作为记者负责报道开幕式。你本应拍照，但整场仪式期间你都睡着了。没办法——你决定作弊，先拍摄大厅的照片，再在照片上画出人物。

为了避免被发现作弊，或为了估算画图所需的时间，你希望知道以下 $Q$ 个值：

• 在时间 $T_j$（$1 \le j \le Q$）时，站在坐标区间 $[L_j, R_j]$（含端点）内的人数。

任务

给定每名参赛者的 迟滞值 以及 $Q$ 个问题的数据，编写一个程序，计算每个问题所满足条件的人数。

输入格式

从标准输入读取以下数据：

• 输入的第一行包含两个由空格分隔的整数 $N$ 和 $Q$。这表示共有 $N$ 名参赛者（不包括 IOI-chan），以及共有 $Q$ 个问题。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $D_i$。这表示从队首数起的第 $i$ 名参赛者的 迟滞值 为 $D_i$。
• 再接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含三个由空格分隔的整数 $T_j$、$L_j$ 和 $R_j$。这些值代表第 $j$ 个问题。

输出格式

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $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

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

2
0

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

1
6
0
5
2
7

提示

样例 1 解释

在本示例输入中，参赛者与 IOI-chan 的移动过程如下。

以下内容中，区间 $[L, R]$ 表示数轴上坐标介于 $L$ 与 $R$ 之间（含端点）的所有点的集合。

• 在时间 $0$，IOI-chan 站在坐标 $0$ 处。第 1、2、3 名参赛者分别站在坐标 $-1$、$-2$ 和 $-3$ 处。
• 在时间 $1$，IOI-chan 移动到坐标 $1$。无参赛者移动；第 1、2、3 名参赛者仍分别站在坐标 $-1$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内无人，第一个问题的输出为 $0$。
• 在时间 $2$，IOI-chan 移动到坐标 $2$。此时 IOI-chan 与第 1 名参赛者之间的距离为 $3$，因此第 1 名参赛者移动到坐标 $1$。第 1、2、3 名参赛者分别站在坐标 $1$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内仅有 IOI-chan，第二个问题的输出为 $1$。
• 在时间 $3$，IOI-chan 移动到坐标 $3$。无参赛者移动；第 1、2、3 名参赛者仍分别站在坐标 $1$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内仅有 IOI-chan，第三个问题的输出为 $1$。
• 在时间 $4$，IOI-chan 移动到坐标 $4$。此时 IOI-chan 与第 1 名参赛者之间的距离为 $3$，因此第 1 名参赛者移动到坐标 $3$。第 1、2、3 名参赛者分别站在坐标 $3$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内有 IOI-chan 和第 1 名参赛者，第四个问题的输出为 $2$。
• 在时间 $5$，IOI-chan 移动到坐标 $5$。无参赛者移动；第 1、2、3 名参赛者仍分别站在坐标 $3$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内仅有第 1 名参赛者，第五个问题的输出为 $1$。
• 在时间 $6$，IOI-chan 移动到坐标 $6$。此时 IOI-chan 与第 1 名参赛者之间的距离为 $3$，因此第 1 名参赛者移动到坐标 $5$。接着，第 1 名与第 2 名参赛者之间的距离变为 $7$，因此第 2 名参赛者移动到坐标 $4$。此外，第 2 名与第 3 名参赛者之间的距离也变为 $7$，因此第 3 名参赛者移动到坐标 $3$。第 1、2、3 名参赛者分别站在坐标 $5$、$4$ 和 $3$ 处。由于区间 $[2, 4]$ 内有第 2 名和第 3 名参赛者，第六个问题的输出为 $2$。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 500\,000$。
• $1 \le Q \le 500\,000$。
• $1 \le D_i \le 1\,000\,000\,000$（$1 \le i \le N$）。
• $1 \le T_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。
• $1 \le L_j \le R_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。

子任务

共有 3 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [7 分]

• $D_i = 1$（$1 \le i \le N$）。

子任务 2 [12 分]

• $N \le 1\,000$。
• $Q \le 1\,000$。
• $T_j \le 1\,000$（$1 \le j \le Q$）。
• $1 \le L_j \le R_j \le 1\,000$（$1 \le j \le Q$）。

子任务 3 [81 分]

无附加约束。

翻译由 Qwen3-235B 完成