Ярослав играет в компьютерную игру, и на одном из уровней перед ним оказалось \(n\) выстроенных в ряд грибов. Каждый гриб имеет свой уровень ядовитости, \(i\)-й с начала гриб имеет уровень ядовитости \(a_i\). Ярослав может выбрать два целых числа \(1 \le l \le r \le n\), а затем его персонаж будет по очереди слева направо поедать грибы из этого подотрезка, то есть грибы с номерами \(l, l+1, l+2, \ldots, r\).
У персонажа есть уровень отравленности \(g\), изначально равный \(0\). Компьютерная игра определяется числом \(x\) — максимальным уровнем отравленности в любой момент времени. При поедании гриба с ядовитостью \(k\) происходит следующее:
- К отравленности персонажа добавляется \(k\).
- Если \(g \leq x\), процесс продолжается, иначе \(g\) становится равным нулю и процесс продолжается.
Ярославу стало интересно, сколько существует способов выбрать значения \(l\) и \(r\) таких, что итоговое значение \(g\) не равно нулю. Помогите Ярославу найти это число!
Выходные данные
Для каждого набора входных данных выведите одно число — количество подотрезков, таких что итоговое значение \(g\) будет не равно нулю.
Примечание
В первом наборе входных данных подходят подотрезки \((1, 1)\), \((1, 2)\), \((1, 4)\), \((2, 2)\), \((2, 3)\), \((3, 3)\), \((3, 4)\) и \((4, 4)\).
Во втором наборе входных данных ненулевое \(g\) останется только на подотрезках \((1, 1)\) и \((2, 2)\).
В третьем наборе входных данных на единственном возможном подотрезке \(g\) будет равно нулю.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 2
1 1 1 1
3 2
1 2 3
1 6
10
6 3
1 2 1 4 3 8
5 999999999
999999999 999999998 1000000000 1000000000 500000000
|
8
2
0
10
7
|