题目描述

译自 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$ 个问题的答案。每个询问都互相独立。

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]$。第三个询问中没有岛屿，因为所有东西都在水下。

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$