一个时限调大的版本：https://qoj.ac/problem/3576
给定 $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 5output
5
1
1
0explanation
例如对于第 $2$ 组询问：$k=4$，大小分别为 $3,7,5$ 的史莱姆进行游戏，则大小为 $7$ 的史莱姆可以先吃掉大小为 $3$ 的史莱姆，此时其大小变为 $10$，然后吃掉大小为 $5$ 的史莱姆从而获胜；可以证明大小为 $3$ 和 $5$ 的史莱姆无法获胜。
样例 2
input
3 2
3 3 3
1 3 1
1 3 0output
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}$