У Пети есть массив \(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\).
В первом примере у следующих отрезки сумма меньше \(4\):
5 4 5 -1 3 4 -1
5
3 0 -1 2 -3
4
4 -1 -2 1 -2 3
3
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач