Fruit Sequences
Description
Zookeeper is buying a carton of fruit to feed his pet wabbit. The fruits are a sequence of apples and oranges, which is represented by a binary string $s_1s_2\ldots s_n$ of length $n$. $1$ represents an apple and $0$ represents an orange.
Since wabbit is allergic to eating oranges, Zookeeper would like to find the longest contiguous sequence of apples. Let $f(l,r)$ be the longest contiguous sequence of apples in the substring $s_{l}s_{l+1}\ldots s_{r}$.
Help Zookeeper find $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$, or the sum of $f$ across all substrings.
The first line contains a single integer $n$ $(1 \leq n \leq 5 \cdot 10^5)$.
The next line contains a binary string $s$ of length $n$ $(s_i \in \{0,1\})$
Print a single integer: $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$.
Input
The first line contains a single integer $n$ $(1 \leq n \leq 5 \cdot 10^5)$.
The next line contains a binary string $s$ of length $n$ $(s_i \in \{0,1\})$
Output
Print a single integer: $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$.
Samples
4
0110
12
7
1101001
30
12
011100011100
156
Note
In the first test, there are ten substrings. The list of them (we let $[l,r]$ be the substring $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
The lengths of the longest contiguous sequence of ones in each of these ten substrings are $0,1,2,2,1,2,2,1,1,0$ respectively. Hence, the answer is $0+1+2+2+1+2+2+1+1+0 = 12$.