F. Фруктовые последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Смотритель зоопарка покупает коробку фруктов чтобы накормить своего любимца кролика. Фрукты в коробке — это последовательность яблок и апельсинов, которая представляется бинарной строкой $$$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$$$ по всем подстрокам.

Входные данные

В первой строке находится единственное целое число $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$.

В следующей строке находится бинарная строка $$$s$$$ длины $$$n$$$ $$$(s_i \in \{0,1\})$$$.

Выходные данные

Выведите единственное целое число: $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$.

Примеры
Входные данные
4
0110
Выходные данные
12
Входные данные
7
1101001
Выходные данные
30
Входные данные
12
011100011100
Выходные данные
156
Примечание

В первом тесте всего есть десять подстрок. Список этих подстрок (мы обозначаем $$$[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$$$.