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

Source: codeforces | Difficulty: VERY_HARD
Tags: Sorting

Amortized analysis

Dynamic programming

Divide and conquer

Data structures


Solutions:
hist = [0] * 1000005

def solve(n, s):
	tot = 0
	cur = 0
	i = 0
	while i < n:
		if s[i] == '0':
			tot += cur
		else:
			l = i
			r = i
			while r + 1 < n and s[r + 1] == '1':
				r += 1
			for x in range(r - l + 1):
				cur += l + x + 1 - hist[x]
				tot += cur
				hist[x] = r - x + 1
			i = r
		i += 1
	return tot
n = int(input())
s = input()
print(solve(n, s))


N = int(input())
S = input()
p = 0
b = [0 for i in range(N + 1)]
a = 0
s = 0
for c in S:
	if c == '0':
		p = 0
		b[0] += 1
	elif p == 0:
		p = 1
		s += b[0] + 1
		b[1] += b[0]
		b[0] = 0
		b[1] += 1
	else:
		p += 1
		s += b[p - 1] + p - 1
		b[p] += b[p - 1]
		b[p - 1] = 1
	a += s
print(a)


from sys import stdin
n = int(stdin.readline())
s = stdin.readline().strip()
total = 0
crnt = 0
hist = [0] * n
i = 0
while i < n:
	if s[i] == '0':
		total += crnt
	else:
		l = i
		r = i
		while r + 1 < n and s[r + 1] == '1':
			r += 1
		for j in range(r - l + 1):
			crnt += l + j + 1 - hist[j]
			total += crnt
			hist[j] = r - j + 1
		i = r
	i += 1
print(total)


n = int(input())
a = 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(acc)


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
	ans += now
print(ans)


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


import sys, io, os
Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(l, h):
	global L, S
	if h - l < 2:
		return L[l] % 2
	m = (l + h) // 2
	c = x = r = s = 0
	d = 1
	for i in range(m - 1, l - 1, -1):
		if L[i] % 2:
			c += 1
			if c > x:
				x = c
			if d:
				r = c
		else:
			c = d = 0
		S[i] = x
		s += x
	c = x = t = 0
	d = e = 1
	p = m - max(1, r)
	w = S[m - 1]
	for i in range(m, h):
		if L[i] % 2:
			c += 1
			if c > x:
				x = c
			if d:
				while S[p] < x + r:
					if p > l:
						v = min(S[p - 1], x + r) - S[p]
					else:
						v = x + r - S[l]
						S[l] = x + r
					s += v * (m - p)
					w += v
					if p > l:
						p -= 1
			else:
				if e < r and w < x:
					w += 1
					s += e
					e += 1
				while S[p] < x:
					if p > l:
						s += (min(S[p - 1], x) - S[p]) * (m - p)
						p -= 1
					else:
						s += (x - S[l]) * (m - l)
						S[l] = x
		else:
			c = d = 0
		t += s
	return t + f(l, m) + f(m, h)
n = int(Z())
S = [0] * n
L = Z()
print(f(0, n))


count = int(input())
s = input()
a = []
add = 0
for i in s:
	if i == '0':
		a.append(0)
		add = 0
	else:
		add += 1
		a.append(add)
b = [0 for i in range(count)]
c = [0 for i in range(count + 1)]
guna = 0
for i in range(count):
	guna = 0
	c[a[i]] += 1
	if a[i] == 0:
		b[i] = 0
	else:
		guna += a[i]
		if c[a[i] - 1] > 0 and a[i] != 1:
			guna += c[a[i] - 1] - 1
			c[a[i]] += c[a[i] - 1] - 1
			c[a[i] - 1] = 1
		elif a[i] == 1:
			guna += c[a[i] - 1]
			c[a[i]] += c[a[i] - 1]
			c[a[i] - 1] = 0
		b[i] = guna
ss = 0
ww = 0
for i in range(count):
	ss += b[i]
	ww += ss
print(ww)


import sys
input = sys.stdin.readline

def prog():
	ans = 0
	curr_total = 0
	last_loc_with_val = [-1] * 500001
	n = int(input())
	s = input().strip()
	i = 0
	while i < n:
		if s[i] == '0':
			ans += curr_total
		else:
			l = i
			r = i
			while r + 1 < n and s[r + 1] == '1':
				r += 1
			for length in range(1, r - l + 2):
				curr_total += l + length - 1 - last_loc_with_val[length]
				ans += curr_total
				last_loc_with_val[length] = r - length + 1
			i = r
		i += 1
	print(ans)
prog()


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


n = int(input())
s = input()
tot = 0
cur = 0
hist = [0] * n
i = 0
while i < n:
	if s[i] == '0':
		tot += cur
	else:
		l = i
		r = i
		while r + 1 < n and s[r + 1] == '1':
			r += 1
		for x in range(r - l + 1):
			cur += l + x + 1 - hist[x]
			tot += cur
			hist[x] = r - x + 1
		i = r
	i += 1
print(tot)


n = int(input())
s = input()
i = 0
ans = 0
curr = 0
prev = [-1] * 500005
while i < n:
	if s[i] == '0':
		ans += curr
	else:
		left = i
		right = i
		while right + 1 < n and s[right + 1] == '1':
			right += 1
		for j in range(right + 1 - left):
			curr += left + j - prev[j]
			ans += curr
			prev[j] = right - j
		i = right
	i += 1
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
n = N()
s = input()
res = 0
x = [-1] * (n + 1)
now = 0
r = 0
while r < n:
	l = r
	if s[r] == '0':
		while r < n and s[r] == '0':
			r += 1
		res += (r - l) * now
	else:
		while r < n and s[r] == '1':
			r += 1
		for k in range(1, r - l + 1):
			now += l + k - 1 - x[k]
			res += now
			x[k] = r - k
print(res)


class SegmentTree:

	def __init__(self, data, default=0, func=max):
		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(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):
		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
	out += add
print(out)


class F:

	def __init__(self, x):
		self.b = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def u(self, i, x):
		while i < len(self.b):
			self.b[i] += x
			i |= i + 1

	def f(self, k):
		i = -1
		for d in reversed(range(len(self.b).bit_length())):
			r = i + (1 << d)
			if r < len(self.b) and k >= self.b[r]:
				i = r
				k -= self.b[i]
		return i + 1
Z = input
n = int(Z())
T = F([0] * n)
t = s = c = 0
L = [*map(int, Z().strip())]
for i in range(n):
	if L[i] % 2:
		c += 1
		T.u(n - 1 - i, 1)
		v = n - 1 - T.f(c)
		s += i - v
		if v >= 0:
			T.u(n - 1 - v, -1)
	else:
		c = 0
	t += s
print(t)


n = int(input())
l = map(int, input())
(c, s, w, p) = ([0] * (n + 3), 0, 0, 0)
for i in l:
	if i == 1:
		p += 1
		s += c[p - 1] + max(1, p - 1)
		c[p] += c[p - 1]
		c[p - 1] = 0
		c[max(1, p - 1)] += 1
	else:
		p = 0
		c[0] += 1
	w += s
print(w)


n = int(input())
s = input()
(res, now, r) = (0, 0, 0)
x = [-1] * (n + 1)
while r < n:
	l = r
	if s[r] == '0':
		while r < n and s[r] == '0':
			r += 1
		res += (r - l) * now
	else:
		while r < n and s[r] == '1':
			r += 1
		for k in range(1, r - l + 1):
			now += l + k - 1 - x[k]
			res += now
			x[k] = r - k
print(res)


import sys
input = sys.stdin.buffer.readline
n = int(input())
s = input().decode()[:n]
(one, rm, pos) = (0, [0] * n, [n] * (n + 1))
for p in range(n - 1, -1, -1):
	u = s[p]
	if u == '1':
		one += 1
		rm[p] = pos[one] - p
	elif one:
		for i in range(one):
			pos[i + 1] = p + i + 1
		one = 0
(sm, mx, one) = (0, 0, 0)
for u in s:
	if u == '1':
		one += 1
	else:
		one = 0
	mx = max(mx, one)
	sm += mx
res = sm
for u in rm:
	sm -= u
	res += sm
print(res)


import os
import sys
from io import BytesIO, IOBase

class SegmentTree:

	def __init__(self, data, default=0, func=max):
		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(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):
		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)

def main():
	n = int(input())
	s = input()
	lastZero = -1
	contiguousOneAfter = [0] * n
	contiguousOneBefore = [0] * n
	for i in range(n):
		if s[i] == '0':
			cnt = 1
			for j in range(i - 1, lastZero, -1):
				contiguousOneAfter[j] = cnt
				cnt += 1
			lastZero = i
	if s[-1] == '1':
		cnt = 1
		for j in range(n - 1, lastZero, -1):
			contiguousOneAfter[j] = cnt
			cnt += 1
	primAns = 0
	curMax = 0
	curCnt = 0
	for i in range(n):
		if s[i] == '1':
			curCnt += 1
		if s[i] == '0':
			curCnt = 0
		if curCnt > curMax:
			curMax = curCnt
		contiguousOneBefore[i] = curCnt
		primAns += curMax
	whenBlocked = [0] * n
	segTree = SegmentTree([0] * (n + 1), 0)
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			whenBlocked[i] = n - segTree.query(contiguousOneAfter[i], n + 1)
			if contiguousOneBefore[i] == 1:
				for j in range(i, i + contiguousOneAfter[i] + 1):
					if n - j >= 0 and n - j <= n and (j < n):
						segTree.__setitem__(contiguousOneBefore[j], n - j)
	ans = primAns
	for i in range(n):
		if s[i] == '1':
			primAns -= whenBlocked[i] - i
		ans += primAns
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
s = input()
f = [n + 1] * (n + 1)
(cur, total, ans) = (0, 0, 0)
for i in range(n - 1, -1, -1):
	if s[i] == '1':
		cur += 1
		total += f[cur] - i - 1
	else:
		while cur:
			f[cur] = i + 1 + cur
			cur -= 1
	ans += total
print(ans)


class F:

	def __init__(self, x):
		self.bit = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def upd(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def find(self, k):
		idx = -1
		for d in reversed(range(len(self.bit).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(self.bit) and k >= self.bit[right_idx]:
				idx = right_idx
				k -= self.bit[idx]
		return idx + 1
import sys, io, os
Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(Z())
T = F([0] * n)
t = s = c = 0
L = Z()
for i in range(n):
	if L[i] % 2:
		c += 1
		T.upd(n - 1 - i, 1)
		v = n - 1 - T.find(c)
		s += i - v
		if v >= 0:
			T.upd(n - 1 - v, -1)
	else:
		c = 0
	t += s
print(t)