Смотритель зоопарка покупает коробку фруктов чтобы накормить своего любимца кролика. Фрукты в коробке — это последовательность яблок и апельсинов, которая представляется бинарной строкой \(s_1s_2\ldots s_n\) длины \(n\). В ней \(1\) обозначает яблоко, а \(0\) обозначает апельсин.
Поскольку у кролика аллергия на апельсины, смотритель зоопарка хочет найти наидлиннейшую подряд идующую подпоследовательность яблок. Пусть \(f(l,r)\) — это наибольшая длина подряд идущей подпоследовательности яблок в подстроке \(s_{l}s_{l+1}\ldots s_{r}\).
Помогите смотрителю зоопарка найти \(\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)\). Другими словами, найдите сумму \(f\) по всем подстрокам.
Выходные данные
Выведите единственное целое число: \(\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)\).
Примечание
В первом тесте всего есть десять подстрок. Список этих подстрок (мы обозначаем \([l,r]\) как подстроку \(s_l s_{l+1} \ldots s_r\)):
- \([1,1]\): 0
- \([1,2]\): 01
- \([1,3]\): 011
- \([1,4]\): 0110
- \([2,2]\): 1
- \([2,3]\): 11
- \([2,4]\): 110
- \([3,3]\): 1
- \([3,4]\): 10
- \([4,4]\): 0
Длины наибольших подряд идущих подпоследовательностей из единиц в этих подстроках \(0,1,2,2,1,2,2,1,1,0\) соответственно. Поэтому ответ \(0+1+2+2+1+2+2+1+1+0 = 12\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0110
|
12
|
|
2
|
7
1101001
|
30
|
|
3
|
12
011100011100
|
156
|