침수

겨울이고 지금까지 이보다 추운 적은 없었다. 말나르 씨는 지난번 아드리아 해 크루즈 여행에서 찍은 사진을 보며 잊지 못할 순간들을 떠올린다. 배경에서는 TV가 해수면 상승을 늦추기 위한 최신 대책안을 보도하고 있다. 해안 사진을 보던 말나르 씨는 해수면이 일정 높이만큼 올랐다면 사진이 어떻게 보였을지 궁금해한다. 사진도 많고 궁금증도 많아서, 말나르 씨는 여러분의 도움을 구한다.

해안을 길이 $n$의 수열 $h_1, h_2, \dots, h_n$으로 나타낸다. 여기서 $h_i$는 $i$번째 지점의 지형 높이이다. 말나르 씨의 질의는 $q$개이며, $i$번째 질의는 다음과 같다. 해수면이 $x_i$미터 상승하면, $l_i$번째 지점부터 $r_i$번째 지점까지의 구간에 섬이 몇 개 있는가?

섬은 모든 $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$번째 질의의 답을 출력한다.

첫 번째 예제의 첫 번째 질의는 왼쪽 그림과 같으며, 섬은 구간 $[2, 2]$와 $[4, 5]$이다. 두 번째 질의의 섬은 구간 $[5, 5]$ 하나이다. 세 번째 질의는 모든 지점이 물에 잠겨 섬이 없다.

두 번째 예제에서 첫 번째 질의의 섬은 $[3, 5]$와 $[8, 9]$이다. 두 번째 질의(오른쪽 그림)의 섬은 $[1, 1]$, $[4, 4]$, $[8, 8]$, $[10, 10]$이다. 세 번째 질의의 섬은 $[1, 1]$, $[3, 4]$, $[8, 10]$이다.