Đã là mùa đông, trời lạnh hơn bao giờ hết, ông Malnar đang xem những bức ảnh của mình từ chuyến du ngoạn cuối cùng trên tàu Adriatic và nhớ lại những khoảnh khắc khó quên. TV đang phát ở chế độ nền, phát tin tức về những đề xuất mới nhất về các biện pháp làm chậm mực nước biển dâng. Nhìn vào những bức ảnh chụp bờ biển của mình, ông Malnar tự hỏi những bức ảnh này sẽ trông như thế nào nếu mực nước biển dâng lên một mức nhất định. Có rất nhiều hình ảnh và thậm chí còn có nhiều câu hỏi hơn nên ông Malnar nhờ các bạn giúp đỡ.

Chúng ta tưởng tượng bờ biển như một dãy ~n~ số ~h_1, h_2, ..., h_n~, trong đó số thứ ~i~ biểu thị chiều cao nổi tại điểm thứ ~i~. Ông Malnar có câu hỏi ~q~, trong đó câu hỏi thứ ~i~ như sau: Sẽ có bao nhiêu hòn đảo nằm giữa điểm thứ ~l_i~ và điểm thứ ~r_i~ nếu mực nước biển dâng lên ~x_i~ mét?

Ảnh bên trái mô tả truy vấn đầu tiên của ví dụ đầu tiên và ảnh bên phải mô tả truy vấn thứ hai của ví dụ thứ hai. Các đảo bên trái tương ứng với các đoạn ~[2, 2]~ và ~[4, 5]~. Các đảo bên phải tương ứng với các đoạn ~[1, 1]~, ~[4, 4]~, ~[8, 8]~ và ~[10, 10]~.

Một hòn đảo được định nghĩa là đoạn tối đa trong đó mọi ~h_i~ đều lớn hơn mực nước biển. đoạn tối đa là đoạn không thể mở rộng theo một trong hai hướng trong khi vẫn giữ đúng điều kiện được đề cập. Ban đầu mực nước biển ở mức ~0~m.

Input

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

Output

Đưa ra ~q~ dòng, dòng thứ ~i~ là một số là câu trả lời cho truy vấn thứ ~i~. Mỗi truy vấn độc lập với những truy vấn khác.

Scoring

1. ~n, q \leq 2\times 10^3~ (10 điểm)

2. ~l_i = 1, r_i = n \space \forall i = 1,2,...,q~ (20 điểm)

3. ~\exists \space p \space (1 \leq p \leq n) \space | \space h_1 \geq h_2 \geq ... \geq h_p~ và ~h_p \leq h_{p+1} \leq ... \leq h_n~ (26 điểm)

4. Không có ràng buộc gì thêm (60 điểm)

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

Explanation

• Ở ví dụ đầu tiên: truy vấn đầu tiên được mô tả ở hình bên trái ở trên, các đảo tương ứng với các đoạn ~[2, 2]~ và ~[4, 5]~; ở truy vấn thứ hai, đảo tương ứng với đoạn ~[5, 5]~, trong truy vấn thứ ba không có hòn đảo nào vì mọi thứ đều ở dưới nước.
• Ở ví dụ thứ hai: trong truy vấn đầu tiên, các đảo tương ứng với các đoạn ~[3, 5]~ và ~[8, 9]~. Trong truy vấn thứ hai (hiển thị ở hình bên phải trong phần mô tả nhiệm vụ), các đảo tương ứng với các đoạn ~[1, 1]~, ~[4, 4]~, ~[8, 8]~ và ~[10, 10]~, trong khi ở các đảo truy vấn thứ ba tương ứng đến các đoạn ~[1, 1]~, ~[3, 4]~ và ~[8, 10]~.