Cho một dãy số độ dài . Ta gọi một vị trí là một vị trí tăng nếu .
Cho truy vấn, mỗi truy vấn được cho bởi ba số nguyên , yêu cầu cộng thêm giá trị vào tất cả các phần tử có vị trí từ đến . Hãy đếm số vị trí tăng sau khi thực hiện xong mỗi truy vấn.
Dữ liệu vào:
Dòng đầu tiên ghi hai số nguyên - độ dài dãy và số truy vấn;
Dòng tiếp theo gồm số nguyên mô tả dãy ;
dòng tiếp theo, dòng thứ gồm ba số nguyên mô tả truy vấn thứ .
Dữ liệu ra:
In ra dòng, dòng thứ cho biết số vị trí tăng sau khi thực hiện xong truy vấn thứ .
Ví dụ:
Dữ liệu vào:
7 3
3 5 4 2 4 6 7
4 6 2
1 4 3
2 2 -5
Dữ liệu ra:
2
3
3
Giải thích:
Sau khi thực hiện xong truy vấn thứ nhất, dãy số trở thành , các vị trí tăng là ;
Sau khi thực hiện xong truy vấn thứ hai, dãy số trở thành , các vị trí tăng là ;
Sau khi thực hiện xong truy vấn thứ ba, dãy số trở thành , các vị trí tăng là .