译自 JOISC 2018 Day2 T3「最悪の記者 3 / Worst Reporter 3」
在 IOI 2018 的入场仪式上，$N$ 位选手站成一排进入会场。我们不妨用数轴上的点来表示选手的位置。
旗手站在排头。开始时（时刻 $0$），旗手的位置为 $0$，$i$ 号选手的位置为 $-i$。旗手与选手们的移动方向均为数轴的正半轴。
我们用 $D_i$ 来描述 $i$ 号选手的缓慢程度。在每一时刻，旗手会向前走 $1$ 单位距离，$1\sim N$ 号选手依次检查他与前面的人的距离。
有 $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\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$。
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：
时刻 2：
时刻 3：
时刻 4：
时刻 5：
时刻 6：
LibreOJ