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

Difficulty: competition

Starter code:

Solutions:
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(list(range(_size))):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


n = int(input())
s = input()

pref = []
curr = 0
for c in s:
    if c == '1':
        curr += 1
    else:
        curr = 0
    pref.append(curr)

suff = []
curr = 0
for c in s[::-1]:
    if c == '1':
        curr += 1
    else:
        curr = 0
    suff.append(curr)
suff.reverse()
    

st = SegmentTree(suff)

out = 0
add = 0
for i in range(n):
    if s[i] == '1':
        lo = -1
        hi =  i - pref[i] + 1
        while hi - lo > 1:
            t = (lo + hi) // 2
            if st.query(t, i - pref[i] + 1) >= pref[i]:
                lo = t
            else:
                hi = t
        add += (i - lo)
    #print(add)
    out += add
print(out)
    


n = int(input())
a = list(map(int, input()))

acc = 0
back = 0
top = 0
cur = 0
s = []

for i,x in enumerate(a):
	if x == 0:
		cur = 0
	else:
		if cur > 0:
			s.pop()
		cur += 1
		if cur >= top:
			top = cur
			back = (cur + 1) * (cur) // 2 + (i - cur + 1) * cur
			s = [(cur, i)]
		else:
			back += i - (s[-1][1] - cur + 1)
			if cur >= s[-1][0]:
				s.pop()
			s += [(cur, i)]
	acc += back
	#print(i,x,acc, back, top, cur)
	#print(s)


print(acc)


import math,sys
n=int(input())
s=input()
dp=[0]*(n+1)
currlength=0
d=[-1]*(n+1)
for i in range(n):
    if s[i]=='0':
        dp[i+1]=dp[i]
        if currlength>0:
            for j in range(currlength):
                d[j+1]=i-j-1
        currlength=0
    else:
        currlength+=1
        numsegs=i-d[currlength]-1
        dp[i+1]=dp[i]+numsegs+1
print(sum(dp))


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)

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().strip()))
def calc(l, r):
    m = (l+r)//2
    if l+1 == r:
        return A[l]
    if l+2 == r:
        return 2*(A[l]+A[l+1])
    X = A[l:m][::-1]
    Y = A[m:r]
    LX = len(X)
    LY = len(Y)
    a1 = [0]*LX
    a2 = [0]*LY
    pre = 1
    cnt = 0
    b1 = 0
    b2 = 0
    for i in range(LX):
        if X[i]:
            cnt += 1
            if pre:
                a1[i] = cnt
                b1 = cnt
            else:
                a1[i] = max(a1[i-1], cnt)
        else:
            pre = 0
            cnt = 0
            a1[i] = a1[i-1]
    pre = 1
    cnt = 0
    for i in range(LY):
        if Y[i]:
            cnt += 1
            if pre:
                a2[i] = cnt
                b2 = cnt
            else:
                a2[i] = max(a2[i-1], cnt)
        else:
            pre = 0
            cnt = 0
            a2[i] = a2[i-1]
    
    
    ra = LX-1
    rb = LY-1
    i = ra
    j = rb
    res = 0
    for _ in range(LX+LY):
        if a1[i] >= a2[j]:
            a = a1[i]
            if b1+b2 <= a:
                res += a*(j+1)
            elif a == b1:
                res += b1*b2 + b2*(b2+1)//2 + (b1+b2)*(j+1-b2)
            else:
                res += a*b2 + (b1+b2-a)*(b1+b2-a+1)//2+(b1+b2)*(j+1-b2)
            i -= 1
            b1 = min(b1, i+1)
        else:
            a = a2[j]
            if b1+b2 <= a:
                res += a*(i+1)
            elif a == b2:
                res += b1*b2 + b1*(b1+1)//2 + (b1+b2)*(i+1-b1)
            else:
                res += a*b1 + (b1+b2-a)*(b1+b2-a+1)//2+(b1+b2)*(i+1-b1)
            j -= 1
            b2 = min(b2, j+1)
        if i == -1 or j == -1:
            break
    return res + calc(l, m) + calc(m, r)

print(calc(0, N))