#D8053. Fruit Sequences
Fruit Sequences
Fruit Sequences
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… 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}… s_{r}.
Help Zookeeper find ∑{l=1}^{n} ∑{r=l}^{n} f(l,r), or the sum of f across all substrings.
Input
The first line contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5).
The next line contains a binary string s of length n (s_i ∈ {0,1})
Output
Print a single integer: ∑{l=1}^{n} ∑{r=l}^{n} f(l,r).
Examples
Input
4 0110
Output
12
Input
7 1101001
Output
30
Input
12 011100011100
Output
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} … s_r):
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.
inputFormat
Input
The first line contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5).
The next line contains a binary string s of length n (s_i ∈ {0,1})
outputFormat
Output
Print a single integer: ∑{l=1}^{n} ∑{r=l}^{n} f(l,r).
Examples
Input
4 0110
Output
12
Input
7 1101001
Output
30
Input
12 011100011100
Output
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} … s_r):
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.
样例
7
1101001
30