Thủy triều

Time limit: 1.0s , Memory limit: 256M , Points: 100 (partial)

Tại một hòn đảo, thủy triều rất bất thường và có thể xảy đến bất cứ thời điểm nào trong ngày. Khi đứng trên thuyền và nhìn vào hòn đảo, thủy triều lên xuống khiến hòn đảo trông như được chia thành các vùng đất nhỏ riêng biệt.

Cấu trúc hòn đảo được biểu thị bởi $n$ ~n~ số nguyên $h_1,h_2,...,h_n$ ~h_1,h_2,...,h_n~, trong đó $h_i$ ~h_i~ là độ cao tại điểm thứ $i$ ~i~ của hòn đảo. Có tổng cộng $q$ ~q~ truy vấn, truy vấn thứ $i$ ~i~ yêu cầu đếm số lượng vùng đất trong khoảng từ $l_i$ ~l_i~ đến $r_i$ ~r_i~ nếu thủy triều dâng đến độ cao $x_i$ ~x_i~.

Một vùng đất được định nghĩa là đoạn điểm liên tiếp tối đa mà các điểm trong đoạn đó đều có độ cao lớn hơn mức thủy triều. Xem thêm hình minh họa dưới đây để hiểu rõ hơn:

Hình bên trái biểu thị truy vấn thứ nhất của ví dụ đầu tiên và hình bên phải biểu thị truy vấn thứ hai của ví dụ thứ hai. Ở hình bên trái, hai vùng đất tương ứng hai đoạn điểm liên tiếp tối đa $[2,2]$ ~[2,2]~ và $[4,5]$ ~[4,5]~. Ở hình bên phải, bốn vùng đất tương ứng bốn đoạn điểm liên tiếp tối đa $[1,1]$ ~[1,1]~, $[4,4]$ ~[4,4]~, $[8,8]$ ~[8,8]~ và $[10,10]$ ~[10,10]~.

Input

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $q$ ~q~ $(1 \le n,q \le 2.10^5)$ ~(1 \le n,q \le 2.10^5)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên $h_1,h_2,...,h_n$ ~h_1,h_2,...,h_n~ $(0 \le h_i \le 10^9)$ ~(0 \le h_i \le 10^9)~.
$q$ ~q~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa ba số nguyên $l_i,r_i$ ~l_i,r_i~ và $x_i$ ~x_i~ $(1 \le l_i \le r_i \le n;0 \le x_i \le 10^9)$ .

Output

Với mỗi truy vấn, in ra câu trả lời trên một dòng.

Samples

Sample Input 1

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

Sample Output 1

2
1
0

Sample Input 2

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

Sample Output 2

2
4
3

Scoring

Subtask $1$ ~1~ với $18\%$ ~18\%~ số điểm: $n,q \le 10^3$ ~n,q \le 10^3~
Subtask $2$ ~2~ với $22\%$ ~22\%~ số điểm: $l_i=1$ ~l_i=1~ và $r_i=n$ ~r_i=n~ với mọi truy vấn
Subtask $3$ ~3~ với $26\%$ ~26\%~ số điểm: Tồn tại chỉ số $p$ ~p~ $(1 \le p \le n)$ ~(1 \le p \le n)~ sao cho $h_1 \ge h2 \ge ... \ge h_p$ ~h_1 \ge h2 \ge ... \ge h_p~ và $h_p \le h_{p+1} \le ... \le h_n$ ~h_p \le h_{p+1} \le ... \le h_n~
Subtask $4$ ~4~ với $34\%$ ~34\%~ số điểm: Không có ràng buộc gì thêm

Clarification

Trong ví dụ thứ nhất, ở truy vấn thứ hai, có một đoạn điểm liên tiếp tối đa là $[5,5]$ ~[5,5]~, ở truy vấn thứ ba, không có vùng đất nào do không có điểm nào có độ cao lớn hơn mức thủy triều.
Trong ví dụ thứ hai, ở truy vấn đầu tiên, có hai vùng đất $[3,5]$ ~[3,5]~ và $[8,9]$ ~[8,9]~, ở truy vấn thứ ba, có ba vùng đất $[1,1]$ ~[1,1]~, $[3,4]$ ~[3,4]~ và $[8,10]$ ~[8,10]~.