Đếm dãy con liên tiếp

Cho dãy số $A$ gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$. Một dãy con liên tiếp của $A$ là dãy các số hạng từ số hạng $a_i$ đến số hạng $a_j$ $(1\le i\le j\le n)$.

Yêu cầu: Hãy cho biết dãy $A$ có bao nhiêu dãy con liên tiếp mà giá trị tuyệt đối của tổng các số hạng trong dãy con đó lớn hơn một số nguyên dương $S$ cho trước.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương $n$ và $S$ $(n\le {10}^5$, $S\le {10}^{14})$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ $(|a_i|\le {10}^9)$.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là số dãy con liên tiếp thỏa mãn yêu cầu của bài toán.

Ràng buộc

• $1\le n\le {10}^5$.
• $1\le S\le {10}^{14}$.
• $|a_i|\le {10}^9$.

Subtasks

• Subtask 1 ($50\%$ số điểm): $n\le 100$.
• Subtask 2 ($30\%$ số điểm): $n\le {10}^3$.
• Subtask 3 ($20\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ