“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 的每个问题，请在单独的一行中输出一个整数，即该问题的答案。

子任务

样例

输入 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