题目描述

译自 COCI 2023/2024 Contest #2 T5「Zatopljenje」

现在是冬天，天气从未如此寒冷，$Malnar$ 先生正看着他上次在亚得里亚海航行时拍摄的照片，回忆着难忘的时刻。电视里正在播放关于减缓海平面上升措施的最新建议的新闻。看着自己拍摄的海岸照片，$Malnar$ 先生问自己，如果海平面上升到一定程度，照片会是什么样子。照片很多，问题更多，因此 $Malnar$ 先生请求你的帮助。

我们把海岸想象成一个由 $n$ 个数字 $h_1, h_2, \ldots, h_n$ 组成的序列。其中第 $i$ 个数字代表第 $i$ 个位置的洋底高度。$Malnar$ 先生有 $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, \ldots, 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

输入

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

输出

2
1
0

题目描述中图片的左图展示了第一个询问，两个岛屿分别是区间 $[2,2]$ 和 $[4,5]$。第二个询问中，岛屿是区间 $[5,5]$。第三个询问中没有岛屿，因为所有东西都在水下。

---

样例 2

输入

10 3
5 0 3 4 2 0 1 6 3 5
3 9 1
1 10 3
1 10 2

输出

2
4
3

第一个询问的两个岛屿是区间 $[3,5]$ 和 $[8,9]$。第二个询问（题目描述中图片的右图）的岛屿是 $[1,1]$、$[4,4]$、$[8,8]$ 和 $[10,10]$。第三个询问的岛屿是区间 $[1,1]$、$[3,4]$ 和 $[8,10]$。

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$n, q \le 2 \cdot 10^3$	9
2	对于所有 $i=1,2,\ldots,q$，满足 $l_i=1, r_i=n$	18
3	存在一个整数 $p\ (1\le p\le n)$，满足 $h_1\ge h_2\ge \ldots \ge h_p$ 且 $h_p\le h_{p+1}\le \ldots\le h_n$
4	无附加限制	55

---