У Пети есть массив \(a\), состоящий из \(n\) целых чисел. Недавно он изучил префикс суммы и теперь умеет быстро считать сумму элементов на любом подотрезке своего массива. Под подотрезком понимается непустая последовательность подряд идущих элементов массива.
Теперь ему стало интересно, сколько в его массиве подотрезков с суммой элементов меньше \(t\). Помогите Пете и определите это количество.
Формально, нужно найти количество пар \(l, r\) (\(l \le r\)), что \(a_l + a_{l+1} + \dots + a_{r-1} + a_r < t\).
Выходные данные
Выведите количество подотрезков в массиве Пети с суммой элементов меньше \(t\).
Примечание
В первом примере у следующих отрезки сумма меньше \(4\):
- \([2, 2]\), сумма на отрезке равна \(-1\)
- \([2, 3]\), сумма на отрезке равна \(2\)
- \([3, 3]\), сумма на отрезке равна \(3\)
- \([4, 5]\), сумма на отрезке равна \(3\)
- \([5, 5]\), сумма на отрезке равна \(-1\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
5 -1 3 4 -1
|
5
|
|
2
|
3 0
-1 2 -3
|
4
|
|
3
|
4 -1
-2 1 -2 3
|
3
|