Cho một dãy số A độ dài N. Ta gọi một vị trí i (1 \leq i < N) là một vị trí tăng nếu A_i > A_i+1.

Cho Q truy vấn, mỗi truy vấn được cho bởi ba số nguyên l, r, x, yêu cầu cộng thêm giá trị x vào tất cả các phần tử có vị trí từ l đến r. Hãy đếm số vị trí tăng sau khi thực hiện xong mỗi truy vấn.

• Dòng đầu tiên ghi hai số nguyên N, Q (1 \leq N, Q \leq 200000) - độ dài dãy A và số truy vấn.
• Dòng tiếp theo gồm N số nguyên A_1, A_2, ..., A_N (1 \leq A_i \leq 10^9) mô tả dãy A.
• Q dòng tiếp theo, dòng thứ i gồm ba số nguyên l_i, r_i, x_i (1 \leq l_i \leq r_i \leq N, |x_i| \leq 10^9) mô tả truy vấn thứ i.

In ra Q dòng, dòng thứ i cho biết số vị trí tăng sau khi thực hiện xong truy vấn thứ i.

• Subtask 1 (40% số điểm): N, Q \leq 2000
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm

• Sau khi thực hiện xong truy vấn thứ nhất, dãy số trở thành 3, 5, 4, 4, 6, 8, 7, các vị trí tăng là 2, 6.
• Sau khi thực hiện xong truy vấn thứ hai, dãy số trở thành 6, 8, 7, 7, 6, 8, 7, các vị trí tăng là 2, 4, 6.
• Sau khi thực hiện xong truy vấn thứ ba, dãy số trở thành 6, 3, 7, 7, 6, 8, 7, các vị trí tăng là 1, 4, 6.