D. Петя и массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Пети есть массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Недавно он изучил префикс суммы и теперь умеет быстро считать сумму элементов на любом подотрезке своего массива. Под подотрезком понимается непустая последовательность подряд идущих элементов массива.

Теперь ему стало интересно, сколько в его массиве подотрезков с суммой элементов меньше $$$t$$$. Помогите Пете и определите это количество.

Формально, нужно найти количество пар $$$l, r$$$ ($$$l \le r$$$), что $$$a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$$$.

Входные данные

В первой строке следуют два целых числа $$$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}$$$) — описание массива Пети. Обратите внимание, что элементы могут быть и отрицательными, и нулевыми, и положительными.

Выходные данные

Выведите количество подотрезков в массиве Пети с суммой элементов меньше $$$t$$$.

Примеры
Входные данные
5 4
5 -1 3 4 -1
Выходные данные
5
Входные данные
3 0
-1 2 -3
Выходные данные
4
Входные данные
4 -1
-2 1 -2 3
Выходные данные
3
Примечание

В первом примере у следующих отрезки сумма меньше $$$4$$$:

  • $$$[2, 2]$$$, сумма на отрезке равна $$$-1$$$
  • $$$[2, 3]$$$, сумма на отрезке равна $$$2$$$
  • $$$[3, 3]$$$, сумма на отрезке равна $$$3$$$
  • $$$[4, 5]$$$, сумма на отрезке равна $$$3$$$
  • $$$[5, 5]$$$, сумма на отрезке равна $$$-1$$$