冬天到了，天气从未如此寒冷。马尔纳先生正在查看他上次在亚得里亚海巡游时的照片，回忆着那些难忘的时刻。背景中电视正在播放关于减缓海平面上升措施的最新提案。看着照片中的海岸，马尔纳先生不禁想，如果海平面上升一定高度，这些照片会是什么样子。照片有很多，问题也更多，所以马尔纳先生请求你的帮助。
我们将海岸想象成一个包含 $n$ 个数字的序列 $h_1, h_2, \dots, h_n$，其中第 $i$ 个数字表示第 $i$ 个点的海拔高度。马尔纳先生有 $q$ 个询问，第 $i$ 个询问如下：如果海平面上升 $x_i$ 米，在第 $l_i$ 个点到第 $r_i$ 个点之间会有多少个岛屿？
左图展示了第一个样例测试数据的第一个询问，右图展示了第二个样例测试数据的第二个询问。左侧的岛屿对应区间 $[2, 2]$ 和 $[4, 5]$。右侧的岛屿对应区间 $[1, 1]$、$[4, 4]$、$[8, 8]$ 和 $[10, 10]$。
岛屿定义为满足所有 $h_i$ 均严格大于海平面的极大区间。极大区间是指在保持上述条件的前提下，无法向任何方向扩展的区间。初始时，海平面高度为 $0$ 米。
输入格式
第一行包含整数 $n$ 和 $q$ ($1 \le n, q \le 2 \cdot 10^5$)，表示序列的长度和询问的次数。
第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($0 \le h_i \le 10^9$)，描述海岸的海拔高度。
接下来的 $q$ 行中，每行包含三个整数 $l_i, r_i$ 和 $x_i$ ($1 \le l_i \le r_i \le n, 0 \le x_i \le 10^9$)，描述第 $i$ 个询问。
输出格式
在 $q$ 行中，第 $i$ 行输出第 $i$ 个询问的答案。每个询问都是相互独立的。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 10 | $n, q \le 2 \cdot 10^3$ |
| 2 | 20 | 对于所有 $i = 1, 2, \dots, q$，满足 $l_i = 1, r_i = n$ |
| 3 | 20 | 存在一个整数 $p$ ($1 \le p \le n$)，使得 $h_1 \ge h_2 \ge \dots \ge h_p$ 且 $h_p \le h_{p+1} \le \dots \le h_n$ |
| 4 | 60 | 无附加限制 |
样例
输入 1
6 3 2 4 2 3 4 1 2 5 2 3 5 3 3 4 4
输出 1
2 1 0
输入 2
10 3 5 0 3 4 2 0 1 6 3 5 3 9 1 1 10 3 1 10 2
输出 2
2 4 3
说明
第一个样例的说明： 第一个询问如题目描述中的左图所示，岛屿对应区间 $[2, 2]$ 和 $[4, 5]$。在第二个询问中，岛屿对应区间 $[5, 5]$。在第三个询问中，没有岛屿，因为所有地方都在水下。
第二个样例的说明： 在第一个询问中，岛屿对应区间 $[3, 5]$ 和 $[8, 9]$。在第二个询问中（如题目描述中的右图所示），岛屿对应区间 $[1, 1]$、$[4, 4]$、$[8, 8]$ 和 $[10, 10]$，而在第三个询问中，岛屿对应区间 $[1, 1]$、$[3, 4]$ 和 $[8, 10]$。