题目描述

Mr. Malnar 有一张地形图，上面画着一个区域内每个位置的海拔高度。具体的，有 $n$ 个位置排成一排，第 $i$ 个位置高出海平面 $h_i$ 米。

海平面可能会上升。给定 $q$ 次询问，对于第 $i$ 次询问你需回答：如果海平面高度上升 $x_i$ 米，那么 $[l_i,r_i]$ 区间中会形成多少个岛？一个岛的定义为一个极长的，每个位置的高度都大于 $x_i$ 的段。

上图分别表示了样例 1 的第一组询问以及样例 2 的第二组询问。左图 $[2,5]$ 区间中有 $[2,2],[4,5]$ 两个岛，而右图中有 $[1,1],[4,4],[8,8],[10,10]$ 四个岛。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $h_{1\sim n}$ 表示每个位置的初始海拔。

接下来 $q$ 行每行 $3$ 个整数 $l_i,r_i,x_i$ 表示一次询问。

输出格式

输出 $q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案。

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

2
1
0

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

2
4
3

提示

数据范围

对于所有数据，$1\le n,q\le 2\times 10^5$，$0\le h_i,x_i\le 10^9$，$1\le l_i\le r_i\le n$。