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 \lt t$.

彼得亚有一个由 $n$ 个整数组成的数组 $a$。他最近学习了前缀和，并因此能够非常快速地计算数组中任意区间的元素之和。这里的“区间”指数组中连续且非空的一段元素。

现在他想知道：他的数组中有多少个区间的元素之和小于 $t$？请帮助彼得亚计算这个数目。

更准确地说，你需要计算满足 $a_l + a_{l+1} + \dots + a_{r-1} + a_r \lt t$ 的数对 $(l, r)$（其中 $l \le r$）的个数。

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$ 的区间的个数。

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$

在第一个例子中，以下区间的元素和小于 $4$：

• $[2, 2]$，元素和为 $-1$
• $[2, 3]$，元素和为 $2$
• $[3, 3]$，元素和为 $3$
• $[4, 5]$，元素和为 $3$
• $[5, 5]$，元素和为 $-1$