Description:
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$$$.
Input Format:
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.
Output Format:
Print the number of segments in Petya's array with the sum of elements less than $$$t$$$.
Note:
In the first example the following segments have sum less than $$$4$$$:
- $$$[2, 2]$$$, sum of elements is $$$-1$$$
- $$$[2, 3]$$$, sum of elements is $$$2$$$
- $$$[3, 3]$$$, sum of elements is $$$3$$$
- $$$[4, 5]$$$, sum of elements is $$$3$$$
- $$$[5, 5]$$$, sum of elements is $$$-1$$$