Hòn đảo

Chúng ta hình dung đường bờ biển như một dãy số \(h_1, h_2, \ldots, h_n\), trong đó \(h_i\) biểu thị độ cao của địa hình tại điểm thứ \(i\). Có \(q\) truy vấn, mỗi truy vấn được mô tả như sau: Có bao nhiêu hòn đảo sẽ xuất hiện khi chỉ xét các điểm từ \(l_i\) đến \(r_i\) nếu mực nước biển dâng lên \(x_i\) mét?

Một hòn đảo được định nghĩa là một đoạn liên tiếp dài nhất (maximal interval) mà mỗi phần tử \(h_i\) trong đoạn đó đều lớn hơn mức nước biển. Một đoạn liên tiếp là dài nhất nếu không thể mở rộng thêm về bên trái hoặc bên phải mà vẫn thỏa điều kiện.

\begincenter

\smallHình minh họa khi xét các điểm từ \(3\) đến \(6\) và mực nước \(x=2\).

\smallVới ví dụ này thì số hòn đảo là \(2\) (\([3,4]\) và \([6,6]\)).

\endcenter

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) --- độ dài của dãy và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \ldots, h_n\) (\(0 \le h_i \le 10^9\)) --- độ cao địa hình.
• Mỗi dòng trong số \(q\) dòng tiếp theo chứa ba số nguyên \(l_i, r_i, x_i\) (\(1 \le l_i \le r_i \le n\), \(0 \le x_i \le 10^9\)) mô tả một truy vấn.

Output

• Ghi ra \(q\) dòng, mỗi dòng chứa số lượng đảo tương ứng với truy vấn thứ \(i\). Các truy vấn là độc lập nhau.

Example

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

Scoring

• Subtask 1 (20 điểm): \(n, q \le 2000\).
• Subtask 2 (20 điểm): \(l_i = 1\), \(r_i = n\) với mọi \(i = 1, 2, \ldots, q\).
• Subtask 3 (10 điểm): Tồn tại một số nguyên \(p\) (\(1 \le p \le n\)) sao cho:
  \(h_1 \ge h_2 \ge \cdots \ge h_p \le h_{p+1} \le \cdots \le h_n.\)
• Subtask 4 (50 điểm): Không có ràng buộc bổ sung.