Вам задан массив \(a_1, a_2, \dots , a_n\), состоящий из чисел от \(0\) до \(9\). Подотрезок этого массива \(a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r\) хороший, если сумма чисел на этом подотрезке равна длине этого подотрезка (\(\sum\limits_{i=l}^{r} a_i = r - l + 1\)).
Например, если \(a = [1, 2, 0]\), то есть \(3\) хороших подотрезка: \(a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0]\) и \(a_{1 \dots 3} = [1, 2, 0]\).
Посчитайте количество хороших подотрезков массива \(a\).
Выходные данные
На каждый набор входных данных выведите ответ — количество хороших подотрезков массива \(a\).
Примечание
Первый набор входных данных рассмотрен в условии.
Во втором наборе входных данных есть \(6\) хороших подотрезков: \(a_{1 \dots 1}\), \(a_{2 \dots 2}\), \(a_{1 \dots 2}\), \(a_{4 \dots 4}\), \(a_{5 \dots 5}\) и \(a_{4 \dots 5}\).
В третьем наборе входных данных есть только один хороший подотрезок: \(a_{2 \dots 6}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
120
5
11011
6
600005
|
3
6
1
|