Let there be an array $b_1, b_2, \ldots, b_k$. Let there be a partition of this array into segments $[l_1; r_1], [l_2; r_2], \ldots, [l_c; r_c]$, where $l_1 = 1$, $r_c = k$, and for any $2 \leq i \leq c$ holds that $r_{i-1} + 1 = l_i$. In other words, each element of the array belongs to exactly one segment.

Let's define the cost of a partition as $$c + \sum_{i = 1}^{c} \operatorname{mex}(\{b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}\}),$$ where $\operatorname{mex}$ of a set of numbers $S$ is the smallest non-negative integer that does not occur in the set $S$. In other words, the cost of a partition is the number of segments plus the sum of MEX over all segments. Let's define the value of an array $b_1, b_2, \ldots, b_k$ as the maximum possible cost over all partitions of this array.

You are given an array $a$ of size $n$. Find the sum of values of all its subsegments.

An array $x$ is a subsegment of an array $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

The input contains several test cases. The first line contains one integer $t$ ($1 \leq t \leq 30$) — the number of test cases.

The first line for each test case contains one integer $n$ ($1 \leq n \leq 100$) — the length of the array.

The second line contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array elements.

It is guaranteed that the sum of the values $n$ over all test cases does not exceed $100$.


-----Output-----

For each test case print a single integer — the answer to the problem.


-----Examples-----

Input
4
2
1 2
3
2 0 1
4
2 0 5 1
5
0 1 1 0 1
Output
4
14
26
48


-----Note-----

In the second test case:

The best partition for the subsegment $[2, 0, 1]$: $[2], [0, 1]$. The cost of this partition equals to $2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0, 1\}) = 2 + 0 + 2 = 4$.

The best partition for the subsegment $[2, 0]$: $[2], [0]$. The cost of this partition equals to $2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0\}) = 2 + 0 + 1 = 3$

The best partition for the subsegment $[2]$: $[2]$. The cost of this partition equals to $1 + \operatorname{mex}(\{2\}) = 1 + 0 = 1$.

The best partition for the subsegment $[0, 1]$: $[0, 1]$. The cost of this partition equals to $1 + \operatorname{mex}(\{0, 1\}) = 1 + 2 = 3$.

The best partition for the subsegment $[0]$: $[0]$. The cost of this partition equals to $1 + \operatorname{mex}(\{0\}) = 1 + 1 = 2$.

The best partition for the subsegment $[1]$: $[1]$. The cost of this partition equals to $1 + \operatorname{mex}(\{1\}) = 1 + 0 = 1$.

The sum of values over all subsegments equals to $4 + 3 + 1 + 3 + 2 + 1 = 14$.

Difficulty: EASY
Tags: Dynamic programming

Complete search

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
for some_random_name in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if a[i] == 0:
			ans += (i + 1) * (n - i) * 2
		else:
			ans += (i + 1) * (n - i)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		if a[i] == 0:
			a[i] = 2
		else:
			a[i] = 1
	ans = 0
	for i in range(n):
		k = 0
		for j in range(i, -1, -1):
			k += a[j]
			ans += k
	print(ans)


for iii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	cou = 0
	for i in range(n):
		if q[i] == 0:
			cou = cou + (i + 1) * (n - i) * 1 + (i + 1) * (n - i) * 1
		else:
			cou = cou + (i + 1) * (n - i)
	print(cou)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans1 = 0
	ans = n * (n + 1) * (n + 2) // 6
	for i in range(n):
		if a[i] == 0:
			ans = ans + (i + 1) * (n - i)
	print(ans1 + ans)


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


for t in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	B = [0 for i in range(n)]
	B[0] = 1 if A[0] == 0 else 0
	for i in range(1, n):
		if A[i] == 0:
			B[i] = B[i - 1] + 1
		else:
			B[i] = B[i - 1]
	(i, ans) = (1, 0)
	while i <= n:
		for j in range(n - i + 1):
			if j == 0:
				ans += i + B[j + i - 1]
			else:
				ans += i + B[j + i - 1] - B[j - 1]
		i += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	nn = list(map(int, input().split()))
	ans = []
	x = 0
	for j in nn:
		if j == 0:
			ans.append(x)
		x += 1
	temp = [nj for nj in range(1, n + 1)]
	t2 = temp[::-1]
	x = [temp[jk] * t2[jk] for jk in range(len(t2))]
	var = 0
	for njk in ans:
		var += (njk + 1) * (n - njk)
	print(sum(x) + var)


from math import *
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	q = 0
	for i in range(0, n):
		p = 0
		for j in range(i, n):
			if l[j] == 0:
				p += 1
			q += abs(i - j) + p
			q += 1
	print(q)


N = int(input())
inputs = []
for i in range(N):
	size = int(input())
	elm = list(map(int, input().split()))
	inputs.append([size, elm])
ans = []
for (size, arr) in inputs:
	cost = 0
	for i in range(size):
		for j in range(i, size):
			cur = arr[i:j + 1]
			zeros = cur.count(0)
			length = j - i + 1
			cost += zeros + length
	ans.append(cost)
for elm in ans:
	print(elm)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(1, n + 1):
		ans += i * (n - i + 1)
	for i in range(n):
		if l[i] == 0:
			ans += (i + 1) * (n - i)
	print(ans)
	t -= 1


def val(l):
	s = 0
	for i in l:
		if i == 0:
			s += 2
		else:
			s += 1
	return s

def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	subarr = []
	for i in range(1, n + 1):
		for j in range(i + 1, n + 2):
			subarr.append(a[i - 1:j - 1])
	x = map(val, subarr)
	return sum(list(x))
t = int(input())
for i in range(t):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = [2 if g == 0 else 1 for g in list(map(int, input().split()))]
	mex = 0
	k = len(a)
	length = len(a)
	for i in range(len(a)):
		n = min(i, len(a) - i - 1)
		mex += k * a[i]
		k += length - 2
		length -= 2
	print(mex)


for z in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	su = 0
	for i in range(1, n + 1):
		su += i * (n + 1 - i)
	for j in range(n):
		if l[j] == 0:
			t = min(j, n - j - 1)
			su += (t + 1) * (2 * n - 2 * t) // 2
	print(su)


def countt(a):
	return len(a) + a.count(0)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(i, n):
			ans += countt(a[i:j + 1])
	print(ans)


for s in [*open(0)][2::2]:
	a = s.split()
	r = i = 0
	for x in a:
		i += 1
		r += (1 + (x == '0')) * i * (len(a) - i + 1)
	print(r)


import sys
from math import *
from functools import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = [0] * n
	p[0] = int(a[0] == 0)
	for i in range(1, n):
		p[i] = p[i - 1] + (a[i] == 0)
	ans = n * (n + 1) * (n + 2) // 6
	for i in range(n):
		ans += (a[i] == 0) * (i + 1) * (n - i)
	print(ans)


def check(n, a):
	total = 0
	for i in range(n):
		d = 0
		for j in range(i, n):
			if a[j] == 0:
				d += 2
			else:
				d += 1
			total += d
	return total
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(n, a))


t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	ans = 0
	for i in range(n):
		ans += (i + 1) * (n - i)
		if a[i] == 0:
			ans += (i + 1) * (n - i)
	print(ans)


I = input
for _ in range(int(I())):
	n = int(I())
	lst = list(map(int, I().split()))
	(res, pre) = (0, 0)
	for (i, n) in enumerate(lst):
		pre += (1 + (n == 0)) * (i + 1)
		res += pre
	print(res)


import math
t = int(input())
while t > 0:
	t -= 1
	ans = 0
	n = int(input())
	a = [int(x) for x in input().split()]
	stack = [0]
	stack2 = []
	gt = 0
	for i in range(0, len(a)):
		if a[i] == 0:
			gt = 2
		if a[i] != 0:
			gt = 1
		stack.append(gt + stack[-1])
	x = 0
	td = int(n // 2) + 1
	for i in range(0, td):
		stack2.append(stack[len(stack) - 1 - x] - stack[0 + x])
		x += 1
	hs = n
	for i in stack2:
		ans += i * hs
		hs -= 2
	print(ans)


def read_single_num():
	return int(input())

def read_nums():
	return list(map(int, input().split()))
t = read_single_num()
for i in range(t):
	n = read_single_num()
	arr = read_nums()
	answer = 0
	for i in range(1, n + 1):
		answer += i * (n - i + 1)
	for (idx, x) in enumerate(arr):
		if x == 0:
			answer += (idx + 1) * (n - idx)
	print(answer)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	p = [0] * (n + 1)
	for i in range(n):
		p[i + 1] = p[i] + int(a[i] == 0)
	s = 0
	r = 0
	for i in range(n):
		for j in range(i + 1):
			r += p[i + 1] - p[j] + i - j + 1
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	arr = [0] * n
	for i in range(n):
		if lst[i] == 0:
			arr[i] = 1
	ans = 0
	for i in range(n):
		for j in range(i, n):
			ans += sum(arr[i:j + 1]) + (j - i + 1)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	res = 0
	for i in range(1, n + 1):
		res = res + i * (n - i + 1)
	for i in range(n):
		if lst[i] == 0:
			res = res + (i + 1) * (n - i)
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	answer = 0
	for i in range(n):
		ans = 0
		for j in range(i, n):
			if arr[j] == 0:
				ans += 1
			ans += 1
			answer += ans
	print(answer)


import math

def modFact(n, p):
	if n >= p:
		return 0
	result = 1
	for i in range(1, n + 1):
		result = result * i % p
	return result

def input_int():
	return int(input())

def input_multiple():
	return map(int, input().split())

def cost(a, n):
	if n < 1:
		return 0
	sum = n
	for i in a:
		if i == 0:
			sum += 1
	return sum
t = input_int()
while t > 0:
	n = input_int()
	a = list(input_multiple())
	sum = 0
	for i in range(n + 1):
		for j in range(i):
			sum += cost(a[j:i], i - j)
	print(sum)
	t -= 1


def get_best_mex(arr):
	return len(arr) + arr.count(0)

def get_weight(arr):
	final_sum = 0
	l = 0
	while l < len(arr):
		r = l + 1
		while r < len(arr) + 1:
			current_sub_section = arr[l:r]
			final_sum += get_best_mex(current_sub_section)
			r += 1
		l += 1
	return final_sum
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(get_weight(arr))


def bst(a):
	c = 0
	for i in range(len(a)):
		if a[i] == 0:
			c = c + 1
	return c * 2 + len(a) - c
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for j in range(1, len(a) + 1):
		for k in range(len(a) - j + 1):
			c = c + bst(a[k:k + j])
	print(c)


def solve(arr):
	arr.sort()
	if arr[0] == 0:
		return len(arr) + arr.count(0)
	else:
		return len(arr)
for _ in range(int(input())):
	n = int(input())
	s = [int(i) for i in input().split()]
	ans = 0
	for i in range(n, -1, -1):
		for j in range(0, i):
			ans += solve(s[j:i])
	print(ans)


def AbhiSolveKiya(n, a):
	ans = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			b = a[i:j]
			zeros = b.count(0)
			ans += len(b) + zeros
	return ans
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(AbhiSolveKiya(n, l))


n = int(input())

def card(n):
	ctr = 0
	for i in range(1, n + 1):
		ctr += i * (n + 1 - i)
	return ctr

def zer(j, l):
	ctr = 0
	for ll in range(1, l + 1):
		first = max(0, j + 1 - ll)
		last = min(l - 1, j - 1 + ll)
		ctr += last - first - ll + 2
	return ctr
for i in range(n):
	l = int(input())
	A = [int(c) for c in input().split(' ')]
	ctr = card(l)
	for (j, a) in enumerate(A):
		if a == 0:
			ctr += zer(j, l)
	print(ctr)


from math import ceil, log2, floor, sqrt, gcd
from collections import defaultdict, deque
from bisect import bisect_left
from collections import defaultdict
import sys
import os.path
sys.setrecursionlimit(200000)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r+')
	sys.stdout = open('output.txt', 'w')

def MI():
	return map(int, input().split())
mod = 10 ** 9 + 7

def solve(testcase):
	n = int(input())
	a = list(MI())
	d = defaultdict(int)
	for i in a:
		d[i] += 1
	c = 0
	ans = 0
	for i in range(n):
		for j in range(i, n):
			ans += j - i + 1
			for k in range(i, j + 1):
				ans += a[k] == 0
	print(ans)
t = int(input())
for _ in range(t):
	solve(_ + 1)


import sys
input = sys.stdin.readline

def solve(n, arr):
	res = 0
	for i in range(n):
		(p, q) = (0, 0)
		for j in range(i, n):
			if not arr[j]:
				p += 1
			q += j - i + 1
			q += p
		res += q
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


t = int(input())
for test_case in range(t):
	n = int(input())
	tally = n * (n + 1) * (n + 2) // 6
	for (i, a) in enumerate(map(int, input().split())):
		if a == 0:
			tally += (i + 1) * (n - i)
	print(tally)


def mex(nList):
	nList = set(nList)
	mex = 0
	while mex in nList:
		mex += 1
	return mex
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		occ = (n - i) * (i + 1)
		m = mex([a[i]])
		ans += (m + 1) * occ
	print(ans)


import sys

def rall():
	return sys.stdin.readlines()

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	_ = rl()
	array = list(map(int, rl().split(' ')))
	n = len(array)
	total = 0
	for i in range(n):
		pts = 2 if array[i] == 0 else 1
		num_segs = (i + 1) * (n - i)
		total += pts * num_segs
	pr(total)


t = int(input())

def funk(n, tab):
	if '0' in tab:
		return len(tab) + tab.count('0')
	else:
		return len(tab)
for i in range(t):
	n = int(input())
	temp = input().split()
	e = 0
	for j in range(1, n + 1):
		for k in range(n - j + 1):
			e += funk(n, temp[k:k + j])
	print(e)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	count = 0
	tmp = 0
	zero_idx = 0
	for i in range(N):
		tmp += i + 1
		count += tmp
		if arr[i] == 0:
			zero_idx += i + 1
		count += zero_idx
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for j in range(1, n + 1):
		for k in range(n - j + 1):
			x = a[k:k + j]
			if 0 in x:
				ans += j + x.count(0)
			else:
				ans += j
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	s = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			s += j - i + m[i:j].count(0)
	print(s)


def solve(n, a):
	total = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			total += j - i + a[i:j].count(0)
	print(total)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	solve(n, a)


for _ in range(0, int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	s = 0
	for i in range(0, n):
		for j in range(i + 1, n + 1):
			x = v[i:j]
			s += x.count(0) + len(x)
	print(s)


for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	m = 0
	d = []
	for k in range(n):
		for j in range(k, n):
			d.append(A[k:j + 1])
	for k in range(len(d)):
		m += len(d[k])
		if 0 in d[k]:
			m += d[k].count(0)
	print(m)


def find(arr):
	result = 0
	for i in range(len(arr)):
		for j in range(len(arr) - i):
			window = arr[j:j + i + 1]
			count = len(window)
			for k in range(len(window)):
				if window[k] == 0:
					count += 1
			result += count
	return result
num = int(input())
for i in range(num):
	n = input()
	arr = [int(x) for x in input().split()]
	print(find(arr))


t = int(input())

def mex(l):
	n = len(l)
	if n <= 1 and 0 not in l:
		return n
	zc = 0
	for i in l:
		if i == 0:
			zc += 1
	return n + zc

def sub_lists(l):
	lists = [[]]
	for i in range(len(l) + 1):
		for j in range(i):
			lists.append(l[j:i])
	return lists
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = sub_lists(a)
	tc = 0
	for i in l:
		tc += mex(i)
	print(tc)


import sys
inp = [a.strip() for a in sys.stdin.readlines()]
t = int(inp[0])
k = 1
for _ in range(t):
	n = int(inp[k])
	k += 1
	l = [int(x) for x in inp[k].split()]
	k += 1
	dp = [0 for i in range(n)]
	dp_0 = [0 for i in range(n)]
	if l[0] == 0:
		dp[0] = 2
		dp_0[0] = 1
	else:
		dp[0] = 1
	for i in range(1, len(l)):
		dp[i] = dp[i - 1] + int((i + 1) * (i + 2) / 2)
		if l[i] == 0:
			dp_0[i] = dp_0[i - 1] + i + 1
		else:
			dp_0[i] = dp_0[i - 1]
		dp[i] += dp_0[i]
	print(dp[-1])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = 0
	xor = 0
	j = 0
	for i in l:
		if i == 0:
			xor = 2
		else:
			xor = 1
		t += (n - j) * (j + 1) * xor
		j += 1
	print(t)


t = int(input())

def solve(ar):
	n = len(ar)
	res = 0
	for i in range(n):
		(nz, tmp) = (0, 0)
		for j in range(i, n):
			nz += int(ar[j] == 0)
			tmp += j - i + 1 + nz
		res += tmp
	return res
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	print(solve(s))


for _ in range(0, int(input())):
	n = int(input())
	mylist = list(map(int, input().split()))
	sum2 = 0
	for i in range(0, n):
		if mylist[i] == 0:
			sum2 = sum2 + (i + 1) * (n - (i + 1) + 1)
	sum1 = n * (n + 1) * (n + 2) / 6
	print(int(sum1 + sum2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dic = {0: []}
	for i in range(len(a)):
		if a[i] == 0:
			dic[0].append(i)
	Sum = 0
	for i in range(n, 0, -1):
		x = i * (i + 1) // 2
		Sum += x
	for i in range(len(dic[0])):
		if dic[0][i] == 0 or dic[0][i] == n - 1:
			Sum += n
		else:
			x = dic[0][i]
			Sum += x + n - x + x * (n - 1 - x)
	print(Sum)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = input().split()
	ans = n * (n + 1) * (n + 2) / 6
	ans = int(ans)
	for i in range(0, n):
		a[i] = int(a[i])
		if a[i] == 0:
			ans = ans + (i + 1) * (n - i)
	print(ans)


n = int(input())
for j in range(0, n):
	cnt = 0
	ans = 0
	a = int(input())
	nums = list(map(int, input().split()))
	for i in range(0, a):
		if nums[i] == 0:
			cnt = cnt + (i + 1) * (a - i)
	ans = ans + cnt
	for i in range(1, a + 1):
		k = i * (a + 1 - i)
		ans = ans + k
	print(ans)


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	arr = [int(char) for char in input().split()]
	ans = 0
	for i in range(n):
		cnt = 0
		for j in range(i, n):
			if not arr[j]:
				cnt += 1
			ans += j - i + 1 + cnt
	return ans
for _ in range(int(input())):
	print(solve())


def solve(l, idx_l, idx_r):
	cnt = 0
	for i in range(idx_l, idx_r):
		if l[i] == 0:
			cnt += 1
	return cnt + idx_r - idx_l
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			ans += solve(a, i, j)
	print(ans)


def maxMex(arr):
	tempArr = [2 if arr[i] == 0 else 1 for i in range(len(arr))]
	s = 0
	for i in range(len(arr)):
		for j in range(i, len(arr)):
			s += sum(tempArr[i:j + 1])
	return s
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(maxMex(arr))


def value(l):
	return len(l) + l.count('0')
for _ in range(int(input())):
	n = int(input())
	l = input().split(' ')
	count = 0
	for i in range(n):
		for j in range(len(l), 0, -1):
			count += value(l[:j])
		l = l[1:]
	print(count)


a = int(input())
for x in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	s = []
	for y in range(b):
		if y == 0:
			if c[y] == 0:
				s.append(1)
			else:
				s.append(0)
		elif c[y] == 0:
			s.append(s[y - 1] + 1)
		else:
			s.append(s[y - 1])
	j = 0
	for y in range(b):
		l = 1
		for z in range(y, b):
			if y == 0:
				j += s[z] + l
			else:
				j += s[z] - s[y - 1] + l
			l += 1
	print(j)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	s = 1
	for i in range(n):
		f = 0
		for j in range(n):
			cl = l[f:f + s]
			zeros = cl.count(0)
			ans += len(cl) + zeros
			f += 1
		n -= 1
		s += 1
	print(ans)


n = int(input())
while n:
	n -= 1
	b = int(input())
	l = list(map(int, input().split(' ')))
	lBig = []
	for i in range(b):
		for j in range(i + 1, b + 1):
			lBig += [l[i:j]]
	ans = 0
	for i in lBig:
		ans += len(i) + i.count(0) * 1
	print(ans)


t = int(input())
for it in range(t):
	n = int(input())
	a = [int(j) for j in input().split(' ')]
	b = []
	for i in range(n):
		if a[i] == 0:
			b.append(i)
	s = (n + 1) * n * (n + 2) // 6
	for i in b:
		for k in range(1, n + 1):
			s += k + min(n - k - i, 0) + min(i + 1 - k, 0)
	print(s)


import sys
import bisect
inp = sys.stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	n = int(inp())
	ans = 0
	a = [int(i) for i in inp().split()]
	for i in range(n):
		c = 0
		for j in range(i, n):
			if a[j] == 0:
				c += 1
			ans += j - i + 1 + c
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	ans = 0
	for i in range(n):
		ans += (i + 1) * (n - i)
		if l[i] == 0:
			ans += (i + 1) * (n - i)
	print(ans)


t = int(input())
for x in range(t):
	n = int(input())
	A = [int(d) for d in input().split()]
	ans = 0
	for a in range(1, n + 1):
		ans += int(a * (a + 1) / 2)
	for a in range(n):
		if A[a] == 0:
			ans += (a + 1) * (n - a)
	print(ans)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(1, n + 1):
			if i + j > n:
				break
			temp = l[i:i + j]
			ans += len(temp) + temp.count(0)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def solve():
	n = int(input())
	a = intlist()
	ans = 0
	for i in range(n):
		if a[i] == 0:
			k = 2
		else:
			k = 1
		ans += k * (i + 1) * (n - i)
	return ans
t = input()
for tt in range(int(t)):
	print(solve())


import sys
from itertools import combinations
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

def inp():
	return int(input())

def read_int_list():
	return list(map(int, input().split()))

def read_list():
	s = input()
	return list(s[:len(s) - 1])

def read_int_map():
	return map(int, input().split())

def sub_segments(a):
	return [a[x:y] for (x, y) in combinations(range(len(a) + 1), r=2)]

def compute(a):
	zeros = 0
	for value in a:
		if value == 0:
			zeros += 1
	return len(a) + zeros

def solve(a):
	return sum([compute(s) for s in sub_segments(a)])
for _ in range(inp()):
	_ = inp()
	print(solve(read_int_list()))


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


def main():
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		a = [int(s) for s in input().split()]
		nums_0 = [0] * (n + 1)
		for i in range(n):
			nums_0[i + 1] = nums_0[i] + 1 if a[i] == 0 else nums_0[i]
		res = 0
		for l in range(1, n + 1):
			for s in range(0, n - l + 1):
				left = s
				right = s + l
				res += l + nums_0[right] - nums_0[left]
		ans.append(res)
	print('\n'.join([str(x) for x in ans]))
main()


import sys
input = sys.stdin.readline
T = int(input())
while T:
	Nbase = int(input())
	baseArr = [int(x) for x in input().split()]
	total = 0

	def calc(N):
		cnt = 0
		for num in arr:
			if num == 0:
				cnt += 1
		return N - cnt + cnt * 2
	for subSeg in range(1, Nbase + 1):
		for offset in range(Nbase - subSeg + 1):
			tempAns = -float('inf')
			arr = baseArr[offset:offset + subSeg]
			total += calc(subSeg)
	print(total)
	T -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	items = list(map(int, input().split()))
	res: int = 0
	for i in range(n):
		zero: int = 0
		for j in range(i, n):
			if items[j] == 0:
				zero += 1
			res += j - i + 1 + zero
	print(res)


def dp(indZero, indNex):
	Ar = [indZero, indNex]
	qX = 0
	for j in Ar:
		qX += j + indZero
	return indNex * indZero
box = [dp]
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	R = 1
	sub_segment = 0
	for L in range(n):
		p = L + R
		q = n - L
		sub_segment += dp(p, q)
		if a[L] == 0:
			sub_segment += dp(p, q)
	print(sub_segment)


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


def deb(n):
	if n < 1:
		return 0
	else:
		return int((n + 1) / 2 * n)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	y = 0
	for i in range(n):
		y += (i + 1) * (n - i)
	r = 0
	for i in range(n // 2 + n % 2):
		r += n - i - 1
		if a[i] == 0:
			y += r + 1 - deb(i - 1)
		if i != n - i - 1:
			if a[n - i - 1] == 0:
				y += r + 1 - deb(i - 1)
	print(y)


def mex(a):
	zc = 0
	for i in a:
		if i == 0:
			zc += 1
	return len(a) + zc
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(len(arr)):
		for j in range(len(arr) - 1, -1, -1):
			ans += mex(arr[i:j + 1])
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(i, n):
			arrray = numbers[i:j + 1]
			ans += len(arrray)
			ans += arrray.count(0)
	print(ans)


def gg(x):
	p = 0
	for a in x:
		if a == 0:
			p = p + 1
	return p
I = lambda : list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	a = I()
	dd = 0
	for l in range(1, n + 1, 1):
		for s in range(0, n - l + 1):
			x = a[s:l + s]
			dd = dd + l + gg(x)
	print(dd)


def F(rr):
	s = 0
	for i in rr:
		if i == 0:
			s += 1
		s += 1
	return s
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	OTBET = 0
	for left in range(n):
		for right in range(left, n):
			OTBET += F(arr[left:right + 1])
	print(OTBET)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0] * n
	for j in range(n):
		for k in range(j, n):
			if a[k] == 0:
				dp[j] += n - k
	result = 0
	for j in range(n):
		result += (n - j) * (n - j + 1) // 2 + dp[j]
	print(result)


def max(array):
	count = 0
	for i in array:
		if i == 0:
			count += 2
		else:
			count += 1
	return count
for a in range(int(input())):
	l = int(input())
	array = list(map(int, input().split()))
	maximum = 0
	for i in range(l):
		for j in range(i + 1, l + 1):
			maximum += max(array[i:j])
	print(maximum)


def max(array):
	count = 0
	for i in array:
		if i == 0:
			count += 2
		else:
			count += 1
	return count
for line in [*open(0)][2::2]:
	array = list(map(int, line.split()))
	maximum = 0
	for i in range(len(array)):
		for j in range(i + 1, len(array) + 1):
			maximum += max(array[i:j])
	print(maximum)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	i = 1
	s = 0
	while i < a + 1:
		j = i
		k = 1
		while j < a + 1:
			s += b[i - 1:j].count(0) + k
			j += 1
			k += 1
		i += 1
	print(s)


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		if i <= (n - 1) // 2:
			dis = i + 1
			count = i * (i + 1)
			count += dis * (n - 2 * i)
			if l[i] == 0:
				ans += count * 2
			else:
				ans += count
		else:
			dis = n - i
			count = (dis - 1) * dis
			count += dis * (n - 2 * (dis - 1))
			if l[i] == 0:
				ans += 2 * count
			else:
				ans += count
	print(ans)
	t = t - 1


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	ans = n * (n + 1) * (n + 2) // 6
	for i in range(1, n + 1):
		if arr[i - 1] == 0:
			ans = ans + i * (n - i + 1)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	res = 0
	for j in range(n):
		res += (j + 1) * (n - j)
		if a[j] == 0:
			res += (j + 1) * (n - j)
	print(res)


t = int(input())
for test in range(t):
	n = int(input())
	result = 0
	listD = [int(x) for x in input().split(' ')]
	for start in range(n):
		counterZero = 0
		for end in range(start, n, 1):
			if listD[end] == 0:
				counterZero += 1
			value = counterZero * 2 + (end - start + 1 - counterZero)
			result += value
	print(result)


import math
import collections
import itertools
import functools

def fun(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ans = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			temp = arr[i:j]
			ans += len(temp)
			for a in temp:
				if a == 0:
					ans += 1
	print(ans)
for tc in range(int(input())):
	fun(tc)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		ans += (n - i) * (n - i + 1) // 2
		if l[i] == 0:
			ans += (i + 1) * (n - i)
	print(ans)