题目描述

译自 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$ 组查询的结果。

样例 1

input

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

output

0
1
1
2
1
2

开始：

时刻 1：

时刻 2：

时刻 3：

时刻 4：

时刻 5：

时刻 6：

样例 2

input

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

output

2
0

样例 3

input

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

output

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$。