Petya and Array

有一个长度为 $n$ 的序列 $a$，和一个数 $t$，求有多少个区间 $[l,r]$ 满足 $a_l+a_{l+1}+...+a_{r} <t $ 且 $l\le r$。

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 $ : - $ [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 $