在 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$ 时，坐标在 $L_j$ 到 $R_j$（包含边界）之间的人数（$1 \le j \le Q$）。

任务

给定每名参赛者的迟钝度以及 $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$ 个询问的答案。

数据范围

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

• $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 分]

• 无附加限制。

样例

样例输入 1

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

样例输出 1

0
1
1
2
1
2

样例输入 2

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

样例输出 2

2
0

样例输入 3

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

样例输出 3

1
6
0
5
2
7