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

from sys import stdin
import sys
import heapq

def bitadd(a,w,bit):
 
    x = a+1
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit):
 
    ret = 0
    x = a+1
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

n = int(stdin.readline())
s = stdin.readline()[:-1]

bit = [0] * (n+10)
dp = [0] * (n+10)

y = 0
ans = 0
for i in range(n):

    if s[i] == "0":
        while y > 0:
            dp[y] += 1
            bitadd(y,y,bit)
            y -= 1
        dp[0] += 1
    else:
        bitadd(y,-1*dp[y]*y,bit)
        bitadd(y+1,-1*dp[y+1]*(y+1),bit)
        dp[y+1] += dp[y]
        dp[y] = 0
        y += 1
        bitadd(y,dp[y]*y,bit)
        
    now = bitsum(i,bit) + (1+y)*y//2
    #print (bitsum(i,bit),(1+y)*y//2,dp)
    ans += now
    
print (ans)

from sys import stdin
import sys
import heapq

def bitadd(a,w,bit):
 
    x = a+1
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit):
 
    ret = 0
    x = a+1
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

n = int(stdin.readline())
s = stdin.readline()[:-1]

bit = [0] * (n+10)
dp = [0] * (n+10)

y = 0
ans = 0
for i in range(n):

    if s[i] == "0":
        while y > 0:
            dp[y] += 1
            bitadd(y,y,bit)
            y -= 1
        dp[0] += 1
    else:
        bitadd(y,-1*dp[y]*y,bit)
        bitadd(y+1,-1*dp[y+1]*(y+1),bit)
        dp[y+1] += dp[y]
        dp[y] = 0
        y += 1
        bitadd(y,dp[y]*y,bit)
        
    now = bitsum(i,bit) + (1+y)*y//2
    #print (bitsum(i,bit),(1+y)*y//2,dp)
    ans += now
    
print (ans)