题目描述

给定 $n$ 只史莱姆排成一列，第 $i$ 只史莱姆的大小为 $a_i$。

对于一些史莱姆，可以进行一局游戏：给定非负整数 $k$，设第 $i$ 只史莱姆可以吃掉第 $j$ 只史莱姆当且仅当 $a_i-a_j\ge k$，此时第 $j$ 只史莱姆被删除而 $a_i$ 变为 $a_i+a_j$；史莱姆之间可以任意互相吃，若没有史莱姆能吃掉其他史莱姆则游戏结束；若最后仅剩下一只史莱姆则这只史莱姆获胜，否则没有史莱姆获胜。

$q$ 次询问 $l,r,k$，求在 $[l,r]$ 这段区间的史莱姆进行游戏的情况下，有多少只史莱姆可能获胜。

注意每组询问之间是独立的，即在询问过程中不会有史莱姆吃掉其他史莱姆。

输入格式

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

第二行，$n$ 个正整数 $a_1,\cdots,a_n$。

之后 $q$ 行，每行两个正整数 $l,r$ 和非负整数 $k$，表示一组询问。

输出格式

共 $q$ 行，每行一个非负整数，表示一组询问的答案。

样例 1

input

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

output

5
1
1
0

explanation

例如对于第 $2$ 组询问：$k=4$，大小分别为 $3,7,5$ 的史莱姆进行游戏，则大小为 $7$ 的史莱姆可以先吃掉大小为 $3$ 的史莱姆，此时其大小变为 $10$，然后吃掉大小为 $5$ 的史莱姆从而获胜；可以证明大小为 $3$ 和 $5$ 的史莱姆无法获胜。

样例 2

input

3 2
3 3 3
1 3 1
1 3 0

output

0
3

样例 3

见下发文件，该样例符合子任务 $6$ 的限制。

数据范围与提示

对于所有数据，$2\le n\le 2\cdot 10^5$，$1\le q\le 2\cdot 10^5$，$1\le a_i\le 10^9$，$1\le l\le r\le n$，$0\le k\le 10^9$。

子任务编号	特殊限制	分值
$1$	$n,q\le 500$	$7$
$2$	$n,q\le 3000$	$15$
$3$	$a_i$ 单调不降	$24$
$4$	$n,q\le 5\cdot 10^4$，$a_i\le 10^6$	$20$
$5$	$n,q\le 10^5$	$19$
$6$	$$	$15$

时间限制：$\texttt{3s}$

空间限制：$\texttt{512MB}$