A binary string A is called *good* if it can be sorted (in non-decreasing order) using the following operation:
Select an i (1 ≤ i ≤ |A| - 1) and swap A_{i} with A_{i + 1}. 

This operation can be performed on any i at most once.

For example, A = 10110 is *good* because we can perform the following operations: 10110 \xrightarrow{i = 1} 01110 \xrightarrow{i = 4} 01101 \xrightarrow{i = 3} 01011 \xrightarrow{i = 2} 00111. On the other hand, A = 11110000 is not *good*.

JJ has a binary string S of length N and wants to find the number of *good* substrings of S out of all its \frac{N \cdot (N + 1)}{2} non-empty substrings. Can you help him?

Note: A string X is a substring of a string Y if X can be obtained from Y by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the length of the binary string S.
- The second line of each test case contains a binary string S of length N containing 0s and 1s only.

------ Output Format ------ 

For each test case, output the number of good substrings of S.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
4
0011
6
111000

----- Sample Output 1 ------ 
10
17

----- explanation 1 ------ 
Test Case 1: $S$ is already sorted. So all its substrings are good.

Test Case 2: Some of the substrings of $S$ which are good are: $000$, $1110$, $100$, $111$.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Amortized analysis

Complete search


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	p1 = p2 = p3 = p4 = n
	for i in reversed(range(n)):
		if s[i] == '1':
			zeros = []
			for j in range(p1, p2):
				if s[j] == '0':
					zeros.append(j)
			if len(zeros) > 1:
				p3 = zeros[0]
				p4 = zeros[1]
			elif len(zeros) == 1:
				p4 = p3
				p3 = zeros[0]
			p2 = p1
			p1 = i
		ans += p4 - i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	caso0 = [0 for i in range(n + 1)]
	caso1 = [0 for i in range(n + 1)]
	(n0, n1) = (-1, -1)
	for i in range(n):
		if i == 0:
			caso0[i + 1] = 0
			caso0[i + 1] = 0
			if s[i] == '0':
				n0 = i
			else:
				n1 = i
		else:
			caso0[i + 1] = n0 + 1
			caso1[i + 1] = n1 + 1
			if s[i] == '0':
				n0 = i
			else:
				n1 = i
	d = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		if i == 0:
			d[i] = 1
		elif s[i] == '1':
			d[i] = 1 + d[i - 1]
		else:
			nex = caso1[caso1[caso0[i + 1]]]
			d[i] = i - nex + 1
		ans += d[i]
	print(ans)


def left_search(A, l, r, tag):
	i = r
	while i >= l and A[i] == tag:
		i -= 1
	return r - i

def backtrace(A):
	(s, b) = (0, 0)
	for r in range(len(A)):
		if r == 0:
			(s, b) = (1, 1)
		else:
			if A[r - 1] == '0' and A[r] == '1' or (A[r - 1] == A[r] and A[r] == '1'):
				b += 1
			elif A[r - 1] == A[r] and A[r] == '0':
				if r + 1 < 3:
					b = 2
				elif A[r - 2] == '0':
					b += 1
				else:
					i = 3
					i += left_search(A, 0, r - i, '0')
					b = i
			else:
				i = 2
				i += left_search(A, 0, r - i, '1')
				i += left_search(A, 0, r - i, '0')
				if i < r + 1:
					i += 1
				i += left_search(A, 0, r - i, '0')
				b = i
			s += b
	return s
t = int(input())
while t > 0:
	n = int(input())
	ba = input()
	(full_zero, full_one) = (True, True)
	for x in ba:
		if x == '1':
			full_zero = False
	for x in ba:
		if x == '0':
			full_one = False
	if full_one or full_zero:
		print(len(ba) * (len(ba) + 1) // 2)
	else:
		ans = backtrace(ba)
		print(ans)
	t -= 1


for i in range(int(input())):
	N = int(input())
	s = str(input())
	ans = 0
	x = y = z = w = N
	for j in reversed(range(N)):
		if s[j] == '1':
			a = []
			for k in range(x, y):
				if s[k] == '0':
					a.append(k)
			if len(a) > 1:
				z = a[0]
				w = a[1]
			elif len(a) == 1:
				w = z
				z = a[0]
			y = x
			x = j
		ans += w - j
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	near0 = [0 for i in range(n + 1)]
	near1 = [0 for i in range(n + 1)]
	(n0, n1) = (-1, -1)
	for i in range(n):
		if i == 0:
			near0[i + 1] = 0
			near0[i + 1] = 0
			if s[i] == '0':
				n0 = i
			else:
				n1 = i
		else:
			near0[i + 1] = n0 + 1
			near1[i + 1] = n1 + 1
			if s[i] == '0':
				n0 = i
			else:
				n1 = i
	dp = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		if i == 0:
			dp[i] = 1
		elif s[i] == '1':
			dp[i] = 1 + dp[i - 1]
		else:
			nxt = near1[near1[near0[i + 1]]]
			dp[i] = i - nxt + 1
		ans += dp[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	ans = 0
	x = y = z = w = n
	for j in reversed(range(n)):
		if s[j] == '1':
			ze = []
			for k in range(x, y):
				if s[k] == '0':
					ze.append(k)
			if len(ze) > 1:
				z = ze[0]
				w = ze[1]
			elif len(ze) == 1:
				w = z
				z = ze[0]
			y = x
			x = j
		ans += w - j
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	res = 0
	W = X = Y = Z = N
	for i in reversed(range(N)):
		if S[i] == '1':
			L = []
			for j in range(X, Y):
				if S[j] == '0':
					L.append(j)
			if len(L) > 1:
				Z = L[0]
				W = L[1]
			elif len(L) == 1:
				W = Z
				Z = L[0]
			Y = X
			X = i
		res += W - i
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	res = 0
	w = x = y = z = n
	for i in reversed(range(n)):
		if s[i] == '1':
			l = []
			for j in range(x, y):
				if s[j] == '0':
					l.append(j)
			if len(l) > 1:
				z = l[0]
				w = l[1]
			elif len(l) == 1:
				w = z
				z = l[0]
			y = x
			x = i
		res += w - i
	print(res)


for tea in range(int(input())):
	n = int(input())
	s = [0]
	wow = list(input())
	for i in wow:
		s.append(int(i))
	c = []
	run = 0
	curr = 0
	for i in s:
		if i == curr:
			run += 1
		else:
			curr = i
			c.append(run)
			run = 1
	c.append(run)
	c[0] -= 1
	ans = 0
	for i in range(len(c)):
		if i % 2 == 0:
			ans += c[i] * (c[i] + 1) // 2
			if i + 1 < len(c):
				ans += c[i] * c[i + 1]
				if i + 2 < len(c):
					if c[i + 1] > 1:
						ans += c[i]
						if i + 3 < len(c) and c[i + 2] == 1:
							ans += c[i] * c[i + 3]
					else:
						ans += c[i] * c[i + 2]
						if i + 3 < len(c):
							ans += c[i] * c[i + 3]
						if i + 4 < len(c):
							ans += c[i]
						if i + 5 < len(c) and c[i + 4] == 1:
							ans += c[i] * c[i + 5]
		else:
			ans += c[i] * (c[i] + 1) // 2
			if i + 1 < len(c):
				ans += c[i + 1] + c[i] - 1
			if i + 2 < len(c):
				if c[i + 1] == 1:
					ans += (c[i] - 1) * c[i + 2]
				ans += c[i + 2]
			if i + 3 < len(c):
				ans += 1
			if i + 4 < len(c) and c[i + 3] == 1:
				ans += c[i + 4]
	print(ans)