“Zhylan.io” 是一款在线多人游戏，玩家在游戏中控制蛇。假设有 $m$ 名玩家参加比赛。给每位玩家分配一个从 $1$ 到 $m$ 的编号。第 $i$ 位玩家控制的蛇长度为 $b_i$。第 $i$ 位玩家的蛇只有在满足条件 $b_i - b_j \ge k$ 时，才能攻击第 $j$ 位玩家（$i \neq j$）的蛇。在这种情况下，玩家 $j$ 被淘汰出局，而第 $i$ 位玩家的蛇长度增加 $b_j$。参数 $k$ 在比赛开始前选定，且在不同比赛中可能不同。
比赛会一直持续，直到无法进行任何攻击为止。如果比赛结束时只剩下一名玩家，则该玩家成为比赛的获胜者。否则，比赛以平局结束，没有获胜者。
Vitya 是“Zhylan.io”的忠实粉丝，拥有丰富的经验。他声称对于任何一场比赛，他都能准确预测出有多少名玩家可能赢得该场比赛。
Batyr 决定测试 Vitya 的能力。于是，他写下了一个长度为 $n$ 的正整数数组 $a$。然后，Batyr 向 Vitya 提出了 $q$ 个如下类型的问题：
- 如果一场由蛇长度为 $(a_l, \dots, a_r)$ 的玩家和参数 $k$ 组成的比赛开始，这些玩家中有多少人可能获胜？
实际上，Vitya 在撒谎，现在他请求你的帮助来回答 Batyr 的问题。请帮帮他。
输入格式
第一行包含两个数字 $n$ 和 $q$ ($2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$)，分别表示数组 $a$ 的大小和 Batyr 提出的问题数量。
第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$)。
接下来 $q$ 行，每行包含三个整数 $l_i, r_i$ 和 $k_i$ ($1 \le l_i < r_i \le n, 0 \le k_i \le 10^9$)，表示问题的描述。
输出格式
对于 Batyr 的每个问题，请在单独的一行中输出一个整数，即该问题的答案。
子任务
| 子任务 | 附加约束 | 分值 | 必要子任务 |
|---|---|---|---|
| 0 | 样例 | 0 | — |
| 1 | $n, q \le 500$ | 7 | 0 |
| 2 | $n, q \le 3000$ | 15 | 1 |
| 3 | $a_1 \le a_2 \le \dots \le a_n$ | 24 | — |
| 4 | $n, q \le 5 \cdot 10^4, a_i \le 10^6$ | 20 | 0 |
| 5 | $n, q \le 10^5$ | 19 | 2, 4 |
| 6 | — | 15 | 3, 5 |
样例
输入 1
6 4 3 1 5 3 7 5 1 6 1 4 6 4 1 4 2 2 3 5
输出 1
5 1 1 0
输入 2
3 2 3 3 3 1 3 1 1 3 0
输出 2
0 3