CF1042D Petya and Array

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 $ .

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 $