Codeforces Round 510 (Div. 2) |
---|
Finished |
Petya has an array $$$a$$$ consisting of $$$n$$$ integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.
Now he wonders what is the number of segments in his array with the sum less than $$$t$$$. Help Petya to calculate this number.
More formally, you are required to calculate the number of pairs $$$l, r$$$ ($$$l \le r$$$) such that $$$a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$$$.
The first line contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$$$).
The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$|a_{i}| \le 10^{9}$$$) — the description of Petya's array. Note that there might be negative, zero and positive elements.
Print the number of segments in Petya's array with the sum of elements less than $$$t$$$.
5 4
5 -1 3 4 -1
5
3 0
-1 2 -3
4
4 -1
-2 1 -2 3
3
In the first example the following segments have sum less than $$$4$$$:
Name |
---|