Read problems statements [Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

For her birthday, Rima got an integer sequence $A_{1}, A_{2}, \dots, A_{N}$. Each element of this sequence is either 1 or 2.

Let's call an integer $s$ ($1 ≤ s ≤ 2N$) a *summary integer* if there is a contiguous subsequence of $A$ such that the sum of its elements is equal to $s$.

Rima wants to count all the summary integers. Can you help her?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the number of summary integers.

------  Constraints  ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 2 \cdot 10^{6}$
$1 ≤ A_{i} ≤ 2$ for each valid $i$

----- Sample Input 1 ------ 
1
3
2 1 2
----- Sample Output 1 ------ 
4

Difficulty: HARD
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = sum(l)
	m1 = 2 * n
	m2 = n
	if p == m1 or p == m2:
		print(n)
	elif l[0] == l[-1] == 2:
		print(p - 1)
	else:
		print(p)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	s = sum(arr)
	if s == n or s == 2 * n:
		print(n)
		continue
	red = 0
	for (a, b) in zip(arr, reversed(arr)):
		if a + b < 4:
			break
		red += 1
	print(s - red)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = sum(l)
	max_sum = 2 * n
	min_sum = n
	if p == max_sum or p == min_sum:
		print(n)
	elif l[0] == l[-1] == 2:
		print(p - 1)
	else:
		print(p)


T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	if 1 not in A:
		print(n)
	elif A[0] + A[-1] == 4:
		print(sum(A) - 1)
	else:
		print(sum(A))


from sys import stdin
input = stdin.readline

def answer():
	(s, one) = (0, False)
	for i in range(n):
		s += a[i]
		if a[i] == 1:
			one = True
	if one == True:
		if a[0] == 2 and a[-1] == 2:
			return s - 1
		else:
			return s
	else:
		return s // 2
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	x = sum(a)
	if not a.__contains__(1):
		print(n)
		return
	elif a[0] == 2 and a[n - 1] == 2:
		print(x - 1)
		return
	else:
		print(x)
		return
try:
	t = int(input())
	for i in range(t):
		solve()
except:
	pass


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	first = None
	last = None
	for i in range(N):
		if A[i] == 1 and first == None:
			first = i
		if A[i] == 1:
			last = i
	if first != None:
		x = min(first, N - last - 1)
		ans.append(sum(A) - x)
	else:
		ans.append(sum(A) // 2)
for i in ans:
	print(i)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	summ = a[0]
	if summ == 1:
		flag = 1
	else:
		flag = 0
	add = 1
	if flag == 1:
		for i in range(1, n):
			summ += a[i]
			add = summ
	else:
		for i in range(1, n):
			if a[i] == 1:
				summ += a[i]
				add = summ
			else:
				summ += a[i]
				add += 1
	print(add)
	t -= 1


def ot(n, a):
	i = 0
	j = n - 1
	while i <= j:
		if a[i] == 1:
			break
		if a[j] == 1:
			break
		i += 1
		j -= 1
	if i > j:
		return n
	total_s = sum(a) - 2 * i
	return total_s + i

def m():
	ans = []
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		ans.append(ot(n, a))
	for x in ans:
		print(x)
m()


test = int(input())
for _ in range(test):
	nof = int(input())
	seq = list(map(int, input().split()))
	s = []
	for i in seq:
		if i not in s:
			s.append(i)
			sum1 = 0
	if len(s) == 1:
		print(len(seq))
	else:
		ind = 0
		while seq[ind] == seq[nof - 1 - ind] == 2:
			ind += 1
		print(sum(seq) - ind)


T = int(input())
for t in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	Sum = sum(A)
	if Sum == N or Sum == 2 * N:
		print(N)
	else:
		ind = 0
		while A[ind] == A[N - 1 - ind] == 2:
			ind += 1
		print(Sum - ind)


for _ in range(int(input())):
	N = int(input())
	array = list(map(int, input().split()))
	p = sum(array)
	oneCount = array.count(1)
	if oneCount == 0:
		print(p // 2)
	elif oneCount == 1:
		k = array.index(1)
		forward = sum(array[:k])
		backward = p - forward - 1
		p -= max(forward, backward) // 2
		print(p)
	else:
		print(p)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if 1 not in arr:
		print(n)
	elif arr[-1] == 1 or arr[0] == 1:
		print(sum(arr))
	else:
		print(sum(arr) - 1)


import sys
tc = int(sys.stdin.readline())
for i in range(tc):
	_ = sys.stdin.readline()
	arr = sys.stdin.readline().split()
	n = len(arr)
	if '1' not in arr:
		print(n)
		continue
	s = 0
	for elem in arr:
		s += 1 if elem == '1' else 2
	f_one = arr.index('1')
	f_one = min(f_one, list(reversed(arr)).index('1'))
	print(s - f_one)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l[-1] == l[0] == 2:
		if sum(l) != 2 * n:
			print(sum(l) - 1)
		else:
			print(n)
	else:
		print(sum(l))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	if len(b) == 1:
		print(n)
	elif a[0] == a[-1] == 2:
		print(sum(a) - 1)
	else:
		print(sum(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	sum1 = [0] * len(a)
	first_index = -1
	last_index = -1
	sum1[0] = a[0]
	for i in range(1, len(a)):
		sum1[i] = sum1[i - 1] + a[i]
	for i in range(len(a)):
		if first_index == -1 and a[i] == 1:
			first_index = i
			last_index = i
		elif a[i] == 1:
			last_index = i
	vv = len(a) - last_index - 1
	if a[0] == 1 or a[len(a) - 1] == 1:
		print(sum(a))
	elif first_index == -1:
		print(n)
	elif first_index == last_index:
		if sum1[last_index] > sum1[len(a) - 1] - sum1[last_index] + a[last_index]:
			an = sum1[last_index] + vv
			print(sum1[last_index] + vv)
		else:
			print(sum1[len(a) - 1] - sum1[last_index] + a[last_index] + last_index)
	elif sum1[last_index] > sum1[len(a) - 1] - sum1[first_index - 1]:
		print(sum1[last_index] + vv)
	else:
		print(sum1[len(a) - 1] - sum1[first_index - 1] + first_index)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	s = sum(A)
	if s == N or s == 2 * N:
		print(N)
	elif A[0] == A[-1] == 2:
		print(s - 1)
	else:
		print(s)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	if len(set(A)) == 1:
		print(N)
	else:
		s = sum(A)
		if A[0] == A[-1] == 2:
			print(s - 1)
		else:
			print(s)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	k = sum(arr)
	if k == 2 * n:
		print(n)
	else:
		s = k
		for i in range(n // 2):
			if arr[i] == 1:
				k -= 2 * i
				break
			elif arr[-(i + 1)] == 1:
				k -= 2 * i
				break
		else:
			k = 1 + k // 2
		print(k + (s - k) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	if len(set(l)) == 1:
		print(n)
	elif l[0] == 2 and l[-1] == 2:
		print(sum(l) - 1)
	else:
		print(sum(l))


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = sum(l)
	i = 0
	while i < n and l[i] == 2:
		i += 1
	j = 0
	while j < n and l[n - 1 - j] == 2:
		j += 1
	print(s - min(i, j))


T = int(input())
while T != 0:
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	if s == N or s == 2 * N:
		print(N)
	elif A[0] == 1 or A[N - 1] == 1:
		print(s)
	else:
		print(s - 1)
	T -= 1


t = int(input())
while t > 0:
	onec = 0
	summ = 0
	li = []
	n = int(input())
	li = list(map(int, input().split()))
	for i in range(0, n):
		k = li[i]
		if k == 1:
			onec += 1
		summ += k
	if onec != 0:
		if li[0] == 2 and li[n - 1] == 2:
			print(summ - 1)
		else:
			print(summ)
	else:
		print(int(summ / 2))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	s = sum(ar)
	if 1 in ar:
		cnt = 0
		for i in range(n):
			if ar[i] != 2 or ar[n - 1 - i] != 2:
				break
			else:
				cnt += 1
		print(s - cnt)
	else:
		print(int(s / 2))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	sum = 0
	for j in range(len(arr)):
		sum = sum + arr[j]
	flag = 0
	for j in range(len(arr)):
		if arr[j] == 1:
			flag = 1
	if flag == 1:
		if arr[0] == 2 and arr[len(arr) - 1] == 2:
			print(sum - 1)
		else:
			print(sum)
	else:
		print(sum // 2)


def m():
	t = int(input())
	while t > 0:
		count = 0
		n = int(input())
		k = 2 * n
		l1 = [0 for i in range(k + 1)]
		l2 = list(map(int, input().split()))
		sum1 = sum(l2)
		if k == sum1:
			print(n)
		elif l2 == [2, 1, 2]:
			print(4)
		else:
			print(sum1)
		t = t - 1
m()


def sum(a):
	s = 0
	for entry in a:
		s = s + entry
	return s
t = int(input())
for i in range(t):
	first = 0
	last = 0
	n = int(input())
	inp = list(map(int, input().split()))
	flag = 0
	for i in range(n):
		if inp[i] == 1:
			first = i
			flag = 1
			break
	for i in range(n):
		if inp[n - 1 - i] == 1:
			last = n - 1 - i
			flag = 1
			break
	if first >= n - last - 1 and flag == 1:
		s = sum(inp[:last + 1]) + n - last - 1
	elif n - last - 1 > first and flag == 1:
		s = sum(inp[first:]) + first
	else:
		s = n
	print(s)


x = int(input())
for i in range(x):
	z = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if l.count(2) != 0:
		if l[0] == 2 and l[-1] == 2 and (l.count(2) != z):
			print(s - 1)
		elif l.count(2) == z:
			print(s // 2)
		else:
			print(s)
	else:
		print(s)


for i in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	ans = 0
	count_of_1 = l.count(1)
	if s % 2 == 0:
		ans = N if count_of_1 == 0 else s
	else:
		ind = l.index(1)
		ans = s if count_of_1 > 1 else s - min(ind, N - 1 - ind)
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	su = sum(a)
	c = a.count(1)
	if su % 2 == 0 and c == 0:
		print(n)
	elif su % 2 == 0 and c != 0:
		print(su)
	elif su % 2 == 1 and c == 1:
		ind = a.index(1)
		you = min(ind, n - 1 - ind)
		print(su - you)
	else:
		print(su)


T = int(input())
while T:
	T -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	c1 = a.count(1)
	s = sum(a)
	if c1 != 0:
		if a[0] == 2 and a[-1] == 2:
			ans = s - 1
		else:
			ans = s
	else:
		ans = n
	print(ans)


T = int(input())
while T:
	T -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = sum(a)
	i = 0
	while i < n:
		if a[i] == 1 or a[n - i - 1] == 1:
			break
		ans -= 1
		i += 1
	print(ans)


def sub_sums(arr):
	sums = [arr[0]]
	for i in range(1, len(arr)):
		sums.append(sums[-1] + arr[i])
	sums.append(arr[1])
	for i in range(2, len(arr)):
		sums.append(sums[-1] + arr[i])
	sums.append(arr[2])
	for i in range(3, len(arr)):
		sums.append(sums[-1] + arr[i])
	if arr[0] != 1 and 1 in arr:
		sums.append(1)
	return set(sums)

def main():
	for _ in range(int(input())):
		N = int(input())
		arr = [int(k) for k in input().split()]
		print(len(sub_sums(arr)))
main()


T = int(input())
while T > 0:
	n = int(input())
	a = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	s = sum(a)
	for i in range(n):
		if a[i] == 2:
			c1 += 1
		else:
			break
	for i in range(n - 1, -1, -1):
		if a[i] == 2:
			c2 += 1
		else:
			break
	s1 = sum(a[c1:])
	s2 = sum(a[:n - c2])
	if c1 == n:
		print(c1)
	else:
		print(int(max(s1, s2) + (s - max(s1, s2)) / 2))
	T -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(1)
	if c != 0:
		i = 0
		while a[i] == 2 and a[n - 1 - i] == 2:
			i += 1
		print(sum(a) - i)
	else:
		print(n)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = sum(a)
	if x == 2 * n:
		print(n)
	elif a == [2, 1, 2]:
		print('4')
	else:
		print(x)


t = int(input())
result = []
for i in range(t):
	n = int(input())
	arr = input().split()
	dup = []
	A = [int(arr[j]) for j in range(n)]
	if sum(A) % 2 != 0:
		if A[0] == 2 and A[-1] == 2:
			result.append(sum(A) - 1)
		else:
			result.append(sum(A))
	elif 1 in A:
		result.append(sum(A))
	else:
		result.append(int(sum(A) / 2))
for i in range(len(result)):
	print(result[i])


t = int(input())
c = 0
s = 0
for i in range(0, t):
	n = int(input())
	a = [int(x) for x in input().split()]
	for j in a:
		s += j
		if j == 1:
			c += 1
	if len(a) == c:
		print(c)
	elif a[0] == 2 and a[n - 1] == 2 and (c > 0):
		print(s - 1)
	elif c == 0:
		print(int(s / 2))
	else:
		print(s)
	c = 0
	s = 0
	a.clear()


t = int(input())
for tes in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	s = 0
	e = 0
	o = 0
	for i in range(n):
		if arr[i] == 1:
			c1 += 1
		else:
			c2 += 1
		s += arr[i]
		if s % 2 == 0:
			e = s
		else:
			o = s
	xx = s
	yy = s
	if s % 2 == 0:
		for i in range(n):
			xx -= arr[i]
			if xx % 2 == 1:
				o = max(o, xx)
			else:
				e = max(e, xx)
	else:
		for i in range(n):
			yy -= arr[i]
			if yy % 2 == 0:
				e = max(e, yy)
			else:
				o = max(o, yy)
	print((o + 1) // 2 + e // 2)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if len(set(arr)) == 1:
		print(n)
	elif arr[0] == 2 and arr[-1] == 2:
		print(sum(arr) - 1)
	else:
		print(sum(arr))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = set()
	flag = 0
	count = 0
	for i in range(n):
		if a[i] == 2 and a[n - i - 1] == 2:
			count += 1
			flag = 1
		else:
			break
	if flag == 1:
		print(sum(a) - count)
	else:
		print(sum(a))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	if 1 not in ls:
		print(n)
	elif ls[0] == 2 and ls[-1] == 2:
		print(sum(ls) - 1)
	else:
		print(sum(ls))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	try:
		n = min(a.index(1), next((i for (i, x) in enumerate(reversed(a)) if x == 1)))
	except ValueError:
		pass
	print(sum(a) - n)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	try:
		n = min(a.index(1), a[::-1].index(1))
	except ValueError:
		pass
	print(sum(a) - n)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if l[0] != 2 or l[n - 1] != 2:
		print(s)
	else:
		c = l.count(1)
		if c > 0:
			first = l.index(1)
			l.reverse()
			last = l.index(1)
			r = min(first, last)
			print(s - r)
		else:
			print(n)


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	A = [int(j) for j in input().split()]
	x = sum(A)
	if x == 2 * n:
		print(n)
	elif A == [2, 1, 2]:
		print(4)
	else:
		print(x)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = sum(l)
	if x == 2 * n:
		print(n)
	elif l == [2, 1, 2]:
		print(4)
	else:
		print(x)


def f():
	t = int(input())
	while t > 0:
		n = int(input())
		sum1 = 0
		k = []
		sum1 = 0
		l = list(map(int, input().split()))
		for i in range(len(l)):
			sum1 = sum1 + l[i]
			k.append(sum1)
		z = sum1
		for i in range(len(k) - 1, -1, -1):
			if k[i] % 2 == 0:
				g2 = k[i]
				break
			else:
				g2 = 0
		for i in range(len(k) - 1, -1, -1):
			if k[i] % 2 != 0:
				g3 = k[i]
				break
			else:
				g3 = 0
		for i in range(len(l)):
			z = z - l[i]
			if z % 2 == 0:
				g4 = z
				break
			else:
				g4 = 0
		z = sum1
		for i in range(len(l)):
			z = z - l[i]
			if z % 2 != 0:
				g5 = z
				break
			else:
				g5 = 0
		if g2 > g4:
			g1 = g2
		else:
			g1 = g4
		if g3 > g5:
			g = g3
		else:
			g = g5
		e = 1 + (g - 1) / 2
		e1 = 1 + (g1 - 2) / 2
		print(int(e + e1))
		t = t - 1
f()


def find_front_one(arr, n):
	count = 0
	for i in range(n):
		if arr[i] == 1:
			break
		count += 1
	return count

def find_back_one(arr, n):
	count = 0
	for i in range(n - 1, -1, -1):
		if arr[i] == 1:
			break
		count += 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	SUM = 0
	arr = list(map(int, input().split()))
	SUM = sum(arr)
	f1 = find_front_one(arr, n)
	f2 = find_back_one(arr, n)
	print(SUM - min(f1, f2))


for _ in range(int(input())):
	n = int(input())
	a = input().split()
	b = ''.join(a)
	a = map(int, a)
	x = b.find('1')
	y = b[::-1].find('1')
	if x == -1:
		x = n
	if y == -1:
		y = n
	print(sum(a) - min(x, y))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	c1 = 0
	c2 = 0
	for i in range(n):
		if arr[i] != 2:
			break
		c1 += 1
	for i in range(n - 1, -1, -1):
		if arr[i] != 2:
			break
		c2 += 1
	print(sum(arr) - min(c1, c2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	check = [0 for x in range(2 * n + 1)]
	s = 0
	tot = sum(a)
	i = 0
	while i < n and a[i] != 1:
		s += a[i]
		i += 1
	if i == n or a[i] == 2:
		for j in range(2, tot + 1, 2):
			check[j] = 1
	else:
		check[1] = 1
		for j in range(1, s + 2):
			check[j] = 1
		for j in range(1, tot - s + 1):
			check[j] = 1
	i = n - 1
	s = 0
	while i >= 0 and a[i] != 1:
		s += a[i]
		i -= 1
	if i == -1 or a[i] == 2:
		for j in range(2, tot + 1, 2):
			check[j] = 1
	else:
		for j in range(1, s + 2):
			check[j] = 1
		for j in range(1, tot - s + 1):
			check[j] = 1
	for j in range(tot, 0, -2):
		check[j] = 1
		if j > 0 and check[j - 1] == 1:
			break
	count = 0
	for i in range(1, tot + 1):
		if check[i]:
			count += 1
	print(count)


for t0 in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	(one, two, f, l) = (0, 0, -1, -1)
	for i in range(n):
		s += a[i]
		if one == 0 and a[i] == 1:
			one = 1
		if two == 0 and a[i] == 2:
			two = 1
		if l == -1 and a[i] == 1:
			l = i
		if a[i] == 1:
			r = i
	if one == 0:
		print(s // 2)
	elif two == 0:
		print(s)
	else:
		print(s - min(l, n - 1 - r))


t = int(input())
for fuck in range(0, t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	tot = sum(arr)
	one = arr.count(1)
	if tot % 2 == 0 and one == 0:
		print(n)
	elif tot % 2 == 1 and one == 1:
		ind = arr.index(1)
		final = min(ind, n - 1 - ind)
		print(tot - final)
	elif tot % 2 == 0 and one != 0:
		print(tot)
	else:
		print(tot)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	cn = a.count(1)
	if cn != 0:
		if a[0] == 2 and a[n - 1] == 2:
			print(sum(a) - 1)
		else:
			print(sum(a))
	else:
		print(sum(a) // 2)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	s1 = sum(l)
	c1 = l.count(1)
	if s1 % 2 == 0 and c1 == 0:
		print(n)
	elif s1 % 2 == 1 and c1 == 1:
		t = l.index(1)
		t = min(t, n - t - 1)
		print(s1 - t)
	else:
		print(s1)


t = int(input())
for ijk in range(0, t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	su = sum(a)
	c = a.count(1)
	if su % 2 == 0 and c == 0:
		print(n)
	elif su % 2 == 0 and c != 0:
		print(su)
	elif su % 2 == 1 and c == 1:
		ind = a.index(1)
		you = min(ind, n - 1 - ind)
		print(su - you)
	else:
		print(su)