No submission language available for this problem.

Description

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