class="math inline">(\mathbf{P}) (paveseq.*)

Cho dãy số nguyên \(a_{1}\), \(a_{2},\ \ldots,\ a_{n}\) và một số nguyên dương \(P\).

Yêu cầu: Đếm số dãy con liên tiếp khác nhau có trung bình cộng lớn hơn hoặc bằng \(P.\)

Dữ liệu vào:

- Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 10^{6})\)

- Dòng hai chứa \(n\) số nguyên \(a_{1}\), \(a_{2},\ \ldots,\ a_{n}\) \((0 \leq a_{i} \leq 10^{9}\))

- Dòng cuối chứa một số nguyên dương \(P\) \((0 \leq P \leq 10^{9}\)).

Dữ liệu ra:

- Ghi một số nguyên không âm duy nhất là kết quả tìm được.

Ví dụ:

Giải thích: Trong ví dụ trên, có 5 dãy con liên tiếp thỏa mãn là: [1, 2], [1,3], [2,2], [2,3], [3,3].

Ràng buộc:

+ Subtask 1: 30% tổng số test có \(n \leq 100.\)

+ Subtask 2: 30% tổng số test tiếp theo có \(101 < n \leq 10^{4}.\)

+ Subtask 3: 40% tổng số test còn lại có \(1\ 001 < n \leq 10^{6}.\)