Đếm đoạn có tổng nhỏ hơn t

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$ gồm $n$ phần tử (có thể âm, $0$ hoặc dương) và một số nguyên $t$.

Hãy đếm số cặp chỉ số $(l,r)$ với $1\le l\le r\le n$ sao cho tổng các phần tử trên đoạn $[l,r]$ nhỏ hơn $t$, tức là:

$$a_l+a_{l+1}+\dots +a_r<t.$$

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $t$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất — số đoạn con liên tiếp có tổng nhỏ hơn $t$.

Ràng buộc

• $1\le n\le 200000$
• $|t|\le 2·{10}^{14}$
• $|a_i|\le {10}^9$

Ví dụ