A12165 | 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$ .
Petya 有一个由 $n$ 个整数组成的数组 $a$ 。他最近学会了部分求和，现在他可以非常快速地计算数组任意段上的元素之和。段是数组中一个挨着一个的非空元素序列。

现在他想知道数组中总和小于 $t$ 的数段有多少。请帮助 Petya 计算这个数字。

更正式地说，您需要计算出 $l, r$ ( $l \le r$ ) 中有多少对是 $a_l + a_{l+1} + \dots + a_{r-1} + a_r \lt 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.
输入

第一行包含两个整数 $n$ 和 $t$ ( $1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$ )。

第二行包含一串整数 $a_1, a_2, \dots, a_n$ ( $|a_{i}| \le 10^{9}$ ) - Petya 的数组描述。请注意，可能存在负、零和正元素。

Print the number of segments in Petya's array with the sum of elements less than $t$ .
输出

打印 Petya 数组中元素总和小于 $t$ 的段的数量。