Cho một dãy gồm \(n\) số nguyên dương \(a_{1},a_{2},...,a_{n}\)và hai số nguyên dương \(m,M\). Mỗi dãy \(a_{i},a_{i + 1},a_{i + 2},...,a_{j}\) với \(1 \leq i \leq j \leq n\) được gọi là dãy con liên tiếp của dãy đã cho.

Yêu cầu: Hãy lập trình đếm số các dãy con liên tiếp của dãy số đã cho có tổng các số lớn hơn hoặc bằng \(m\) và nhỏ hơn hoặc bằng \(M\).

Dữ liệu vào:

+ Dòng đầu ghi ba số nguyên \(n,m,M\left( 1 \leq n \leq 10^{5};1 \leq m,M \leq 10^{18},m < M \right);\)

+ Dòng thứ hai ghi n số nguyên \(a_{1},a_{2},...,a_{n}\left( 1 \leq a_{i} \leq 1000,i = 1,2,...,n \right).\)

Kết quả:

+ Ghi một số nguyên là số các dãy con liên tiếp thỏa mãn có tổng các số lớn hơn hoặc bằng \(m\) và nhỏ hơn hoặc bằng \(M\).

Ví dụ:

Giải thích:

• Test 1: Các dãy con thỏa mãn là: 3 2; 2 4; 4 2; 3 2 4; 2 4 2; 4 2 1; 2 1 2; 2 4 2 1; 4 2 1 2.

Ràng buộc:

• Có \(\frac{2}{5}\) số test của bài thỏa mãn: \(1 < n \leq 100,M \leq 10^{9};\)

• \(\frac{2}{5}\) số test khác của bài thỏa mãn: \(100 < n \leq 5000,M \leq 10^{9};\)

• \(\frac{1}{5}\) số test còn lại của bài thỏa mãn: \(5000 < n \leq 100000,M \leq 10^{18}.\)