Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

divide and conquer

dp

two pointers

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Fruit Sequences

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputZookeeper 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.

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)$$$.

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} \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$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 07:39:34 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|