You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

跑操（$\texttt{run}$）

【题目描述】

小 D 的学校的操场上有 $n+1$ 个学生在跑操，他们的编号依次为 $0,1,\dots,n$。

操场可以被看成一根无限长的一维数轴，对于第 $i$ 个人，其初始位置在 $-i$ 上。

每秒内，学生会按 $0,1,\dots n$ 的顺序依次按如下规则移动：

• 第 $0$ 个学生每秒向正方向移动 $1$ 的距离。
• 第 $i$ 个学生（$1\le i\le n$）如果与第 $i-1$ 的学生的距离 $>d_i$，那么他会移动到第 $i-1$ 个学生的上一个位置。

小 D 突然想到了 $q$ 个询问，第 $i$ 个询问需要你求出第 $t_i$ 秒在 $[l_i,r_i]$ 范围内的学生数量。

你能回答小 D 的 $q$ 个询问吗？

【输入格式】

从 $\texttt{run.in}$ 中读入数据。

第一行两个整数 $n,q$。

第二行 $n$ 个整数，第 $i$ 个正整数表示 $d_i$。

接下来 $q$ 行，每行三个整数，分别表示 $t_i,l_i,r_i$。

【输出格式】

输出到 $\texttt{run.out}$ 中。

输出 $q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次询问的答案。

【样例 1 输入】

3 2
1 2 2
1 1 5
2 0 1

【样例 1 输出】

1
2

【样例 1 解释】

四个学生的位置变化如下：

• 第 $0$ 秒：$[0,-1,-2,-3]$。
• 第 $1$ 秒：$[1,0,-2,-3]$。
• 第 $2$ 秒：$[2,1,0,-1]$。

【样例 2】

见下发文件中的 $\texttt{run2.in}$ 与 $\texttt{run2.ans}$。

【样例 3】

见下发文件中的 $\texttt{run3.in}$ 与 $\texttt{run3.ans}$。

【数据范围】

对于所有测试数据有：$1\le n,q\le5 \times 10^5,1\le d_i,t_i\le 10^9,0\le l_i\le r_i\le 10^9$。