You are given a binary array$^{\dagger}$ of length $n$. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a $0$ into a $1$ or vice-versa.

What is the maximum number of inversions$^{\ddagger}$ the array can have after performing at most one operation?

$^\dagger$ A binary array is an array that contains only zeroes and ones.

$^\ddagger$ The number of inversions in an array is the number of pairs of indices $i,j$ such that $i<j$ and $a_i > a_j$.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the array.

The following line contains $n$ space-separated positive integers $a_1$, $a_2$,..., $a_n$ ($0 \leq a_i \leq 1$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, output a single integer  — the maximum number of inversions the array can have after performing at most one operation.


-----Examples-----

Input
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1
Output
3
7
1
13
2


-----Note-----

For the first test case, the inversions are initially formed by the pairs of indices ($1, 2$), ($1, 4$), ($3, 4$), being a total of $3$, which already is the maximum possible.

For the second test case, the inversions are initially formed by the pairs of indices ($2, 3$), ($2, 4$), ($2, 6$), ($5, 6$), being a total of four. But, by flipping the first element, the array becomes ${1, 1, 0, 0, 1, 0}$, which has the inversions formed by the pairs of indices ($1, 3$), ($1, 4$), ($1, 6$), ($2, 3$), ($2, 4$), ($2, 6$), ($5, 6$) which total to $7$ inversions which is the maximum possible.

Source: codeforces | Difficulty: EASY
Tags: Data structures

Mathematics

Greedy algorithms


Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = input()
	l = l[::2]
	if '0' not in l:
		print(n - 1)
	elif '1' not in l:
		print(n - 1)
	else:
		ma = l.find('0')
		mi = l.rfind('1')
		t2 = l[ma + 1:].count('0')
		t3 = l[:mi].count('1')
		vc0 = l.count('0')
		u1 = -ma + t2
		u2 = -(n - mi - 1) + t3
		vs0 = 0
		count = 0
		for j in l:
			if j == '1':
				count += vc0 - vs0
			else:
				vs0 += 1
		print(max(count + u1, count + u2, count))


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = sys.stdin.readline().split()
	ans = 0
	an2 = ji2 = an = ji = 0
	f1 = 1
	for i in a:
		if i == '1':
			ji += 1
		else:
			an += ji
		if f1 and i == '0':
			ji2 += 1
			f1 = 0
		elif i == '1':
			ji2 += 1
		else:
			an2 += ji2
	ans = max(ans, an, an2)
	an = ji = 0
	f2 = 1
	for i in range(n - 1, -1, -1):
		if f2 and a[i] == '1':
			a[i] = '0'
			break
	for i in a:
		if i == '1':
			ji += 1
		else:
			an += ji
	ans = max(ans, an)
	print(ans)


import sys
input = sys.stdin.readline
nel = int(input())
for iline in range(nel):
	input()
	line = list(map(int, input().split(' ')))
	prec_ones = 0
	prec_ones_with_0inv = 0
	prec_ones_with_1inv = 0
	first_0 = False
	poss = 0
	poss_with_0inv = 0
	poss_with_1inv = 0
	try:
		ilast1 = len(line) - line[::-1].index(1) - 1
	except:
		ilast1 = -1
	for (iel, el) in enumerate(line):
		if el == 1:
			if iel == ilast1:
				poss_with_1inv += prec_ones_with_1inv
			else:
				prec_ones_with_1inv += 1
			prec_ones += 1
			prec_ones_with_0inv += 1
		else:
			poss += prec_ones
			poss_with_1inv += prec_ones_with_1inv
			if not first_0:
				prec_ones_with_0inv += 1
				first_0 = True
			else:
				poss_with_0inv += prec_ones_with_0inv
	print(max(max(poss, poss_with_0inv), poss_with_1inv))


import sys
input = sys.stdin.readline

def solution():
	T = int(input())
	for t in range(T):
		N = int(input())
		num = list(map(int, input().split()))
		(cnt, oneCnt) = (0, 0)
		for i in range(N):
			if num[i] == 1:
				oneCnt += 1
			else:
				cnt += oneCnt
		answer = cnt
		(leftIdx, rightIdx) = (-1, -1)
		for i in range(N):
			if num[i] == 0:
				leftIdx = i
				break
		for i in range(N - 1, -1, -1):
			if num[i] == 1:
				rightIdx = i
				break
		num[leftIdx] = 1
		(cnt, oneCnt) = (0, 0)
		for i in range(N):
			if num[i] == 1:
				oneCnt += 1
			else:
				cnt += oneCnt
		answer = max(cnt, answer)
		num[leftIdx] = 0
		num[rightIdx] = 0
		(cnt, oneCnt) = (0, 0)
		for i in range(N):
			if num[i] == 1:
				oneCnt += 1
			else:
				cnt += oneCnt
		answer = max(answer, cnt)
		print(answer)
solution()


def inversion_checker(string):
	number_one = 0
	number_inversion = 0
	for item in string:
		if item == 0:
			number_inversion += number_one
		elif item == 1:
			number_one += 1
	return number_inversion

def first_zero_flip(string):
	for item in string:
		if item == 0:
			string[string.index(item)] = 1
			break
	return string

def last_one_flip(string):
	rev = string[::-1]
	for item in rev:
		if item == 1:
			rev[rev.index(item)] = 0
			break
	return rev[::-1]
answer = []
for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	dup = s.copy()
	original_string = inversion_checker(s)
	first_zero = inversion_checker(first_zero_flip(s))
	last_one = inversion_checker(last_one_flip(dup))
	answer.append(max(original_string, first_zero, last_one))
print(*answer, sep='\n')


for a in [*open(0)][2::2]:
	a = [*map(int, a.split())]
	ans = 0
	z = 0
	n = len(a)
	for i in a:
		z += i
		if i == 0:
			ans += z
	x = ans
	for i in range(len(a)):
		if a[i] == 0:
			ans = max(ans, ans - i + n - z - 1)
			break
	for i in range(len(a) - 1, -1, -1):
		if a[i] == 1:
			ans = max(ans, x - n + i + z)
	print(ans)


def f(a):
	a = a[::-1]
	s = 0
	z = 0
	for i in a:
		if i:
			s += z
		else:
			z += 1
	return s
t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	a1 = a[:]
	a2 = a[:]
	if 0 in a:
		a1[a.index(0)] = 1
	if 1 in a:
		a2[-(a[::-1].index(1) + 1)] = 0
	print(max(f(a), f(a1), f(a2)))
	t -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	zeros = a.count(0)
	ones = a.count(1)
	rem_zeros = zeros
	invs = 0
	first0 = -1
	if zeros > 0:
		first0 = a.index(0)
	last1 = -1
	for i in range(n):
		if a[i] == 1:
			invs += rem_zeros
			last1 = i
		else:
			rem_zeros -= 1
	change0 = 0
	if zeros > 0:
		change0 = max(0, zeros - 1 - first0)
	change1 = 0
	if ones > 0:
		change1 = max(0, ones - 1 - (n - last1 - 1))
	print(invs + max(change0, change1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c0 = 0
	c1 = 0
	p0 = -1
	p1 = -1
	ans = 0
	for i in range(n - 1, -1, -1):
		if a[i] == 0:
			c0 += 1
			p0 = i
		else:
			if c1 == 0:
				p1 = i
			c1 += 1
			ans += c0
	print(max(ans, ans + (c0 - 1) - p0, ans - (n - p1 - 1) + (c1 - 1)))


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	inversions = 0
	zeroes = 0
	for i in range(n - 1, -1, -1):
		if l[i] == 0:
			zeroes += 1
		else:
			inversions += zeroes
	ones = 0
	maxgains = 0
	for i in range(n):
		if l[i] == 0:
			zeroes -= 1
			if maxgains < zeroes - ones:
				maxgains = zeroes - ones
		else:
			if maxgains < ones - zeroes:
				maxgains = ones - zeroes
			ones += 1
	print(inversions + maxgains)
t = int(input())
for _ in range(t):
	solve()


def count(x, sm, n):
	total = 0
	for i in range(n):
		if x[i] == 1:
			sm -= 1
			total += n - 1 - i - sm
	return total

def main(n, x):
	sm = sum(x)
	(a, b) = (0, 0)
	for i in range(n):
		if x[i]:
			a -= 1
		else:
			a += n - sm - 1
			break
	for i in range(n - 1, -1, -1):
		if x[i] == 0:
			b -= 1
		else:
			b += sm - 1
			break
	if a < 0 and b < 0:
		return count(x, sm, n)
	elif a < b:
		return count(x, sm, n) + b
	else:
		return count(x, sm, n) + a
t = int(input())
for i in range(t):
	n = int(input())
	print(main(n, list(map(int, input().split()))))


def inverse(arr):
	(ans, ones) = (0, 0)
	for i in arr:
		if i == 1:
			ones += 1
		else:
			ans += ones
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	result = inverse(arr)
	tag = None
	for i in range(n):
		if arr[i] == 0:
			arr[i] = 1
			tag = i
			break
	result = max(result, inverse(arr))
	if tag != None:
		arr[tag] = 0
	for i in range(n - 1, -1, -1):
		if arr[i] == 1:
			arr[i] = 0
			break
	print(max(result, inverse(arr)))


for jj in range(int(input())):
	n = int(input())
	arr = input().split()
	k = arr.count('1')
	m = n - k
	if k == 0 or m == 0:
		print(n - 1)
		continue
	(x, y) = (k, m)
	a = b = -1
	res = 0
	for i in range(n):
		if arr[i] == '0':
			if a == -1:
				a = i
			y -= 1
		else:
			b = i
			res += y
	print(max(res, res + m - 1 - a, res + k - 1 - (n - b - 1)))


def maximum_numb_inversions(lst):
	max_numb_1 = 0
	inversion_count_1 = 0
	first_zero = False
	for number in lst:
		if number == 1:
			inversion_count_1 += 1
		elif first_zero == False:
			inversion_count_1 += 1
			first_zero = True
		else:
			max_numb_1 += inversion_count_1
	max_numb_2 = 0
	inversion_count_2 = 0
	first_one = False
	for number in lst[::-1]:
		if number == 0:
			inversion_count_2 += 1
		elif first_one == False:
			inversion_count_2 += 1
			first_one = True
		else:
			max_numb_2 += inversion_count_2
	max_numb_3 = 0
	inversion_count_3 = 0
	for number in lst:
		if number == 1:
			inversion_count_3 += 1
		else:
			max_numb_3 += inversion_count_3
	return max(max_numb_1, max_numb_2, max_numb_3)
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	print(maximum_numb_inversions(lst))


import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s.strip())

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	arr = inlt()
	pref = []
	suf = []
	o = 0
	oo = 0
	val = 0
	for i in arr:
		if i == 0:
			o += 1
			val += oo
		else:
			oo += 1
	ans = 0
	oo = 0
	switch = True
	for i in arr:
		if i == 1:
			oo += 1
		elif switch:
			oo += 1
			switch = False
		else:
			ans += oo
	val = max(ans, val)
	ans = 0
	switch = True
	o = 0
	for i in arr[::-1]:
		if i == 0:
			o += 1
		elif switch:
			o += 1
			switch = False
		else:
			ans += o
	print(max(ans, val))


def inverse_couny(arr):
	cnt1 = 0
	cnt2 = 0
	for i in arr:
		if i == 1:
			cnt1 += 1
		else:
			cnt2 += cnt1
	return cnt2
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr_cop = arr[:]
	c1 = inverse_couny(arr)
	for i in range(n):
		if arr[i] == 0:
			arr[i] = 1
			break
	c2 = inverse_couny(arr)
	for i in range(n - 1, -1, -1):
		if arr_cop[i] == 1:
			arr_cop[i] = 0
			break
	c3 = inverse_couny(arr_cop)
	print(max(c1, c2, c3))


t = int(input())
for t1 in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = n - 1
	zcount = 0
	count = 0
	lastzero = 0
	fone = 0
	while i >= 0:
		if a[i] == 0:
			zcount += 1
			lastzero = i
		else:
			if i > fone:
				fone = i
			count += zcount
		i -= 1
	if zcount == 0 or zcount == n:
		print(n - 1)
	else:
		if fone - zcount > zcount - lastzero - 1:
			if fone > zcount:
				count += fone - zcount
		elif zcount > lastzero + 1:
			count += zcount - lastzero - 1
		print(count)


def f():
	T = int(input())
	for _ in range(T):
		_ = input()
		nums = [int(c) for c in input().split()]
		print(solve(nums))

def solve(nums):
	original = count_inversions(nums)
	flip_first_zero = 0
	flip_last_one = 0
	first_zero = -1
	last_one = -1
	for i in range(len(nums)):
		x = nums[i]
		if x == 0:
			if first_zero == -1:
				first_zero = i
		else:
			last_one = i
	if first_zero != -1:
		clone = nums[:]
		clone[first_zero] = 1
		flip_first_zero = count_inversions(clone)
	if last_one != -1:
		clone = nums[:]
		clone[last_one] = 0
		flip_last_one = count_inversions(clone)
	return max(original, flip_first_zero, flip_last_one)

def count_inversions(nums):
	ones = 0
	res = 0
	for x in nums:
		if x == 0:
			res += ones
		else:
			ones += 1
	return res
f()


def pos(a):
	ones = 0
	s = 0
	for i in a:
		if i == 1:
			ones += 1
		else:
			s += ones
	return s
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i1 = pos(a)
	zrep = orep = 0
	b = a.copy()
	for i in range(n):
		if b[i] == 0:
			b[i] = 1
			zrep = pos(b)
			break
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			a[i] = 0
			orep = pos(a)
			break
	print(max(i1, zrep, orep))


for _ in range(int(input())):
	n = int(input())
	num = [int(x) for x in input().split()]
	if len(set(num)) == 1:
		print(n - 1)
	else:
		(n1, n0, n0s, n1s, r) = (0, num.index(0), 0, 0, 0)
		for i in range(n):
			if num[i] == 1:
				n1 = i
				n1s += 1
			else:
				n0s += 1
				r += n1s
		r0 = r + (n0s - 1) - n0
		r1 = r + n1s - 1 - (n - 1 - n1)
		print(max(r0, r1, r))


def invs(array):
	null = array.copy()
	one = array.copy()
	(a, b, c) = (0, 0, inversions(array))
	for i in range(len(array) - 1, -1, -1):
		if array[i] == 1:
			null[i] = 0
			a = inversions(null)
			break
	for i in range(0, len(array)):
		if array[i] == 0:
			one[i] = 1
			b = inversions(one)
			break
	print(max(a, b, c))

def inversions(array):
	ones = 0
	inv = 0
	for i in array:
		if i == 1:
			ones += 1
		if i == 0:
			inv += ones
	return inv
for set in range(int(input())):
	n = int(input())
	mass = [int(x) for x in input().split()]
	invs(mass)


count = int(input())

def CountInversions(bList):
	oneCount = 0
	inversionsCount = 0
	for i in bList:
		if i == 1:
			oneCount += 1
		else:
			inversionsCount += oneCount
	return inversionsCount
for i in range(count):
	numsCount = int(input())
	binaryList = [int(e) for e in input().split(' ')]
	inv0 = CountInversions(binaryList)
	changedIndex = -1
	for i in reversed(range(numsCount)):
		if binaryList[i] == 1:
			binaryList[i] = 0
			changedIndex = i
			break
	inv1 = CountInversions(binaryList)
	if changedIndex > -1:
		binaryList[changedIndex] = 1
	for i in range(numsCount):
		if binaryList[i] == 0:
			binaryList[i] = 1
			changedIndex = i
			break
	inv2 = CountInversions(binaryList)
	print(max([inv0, inv1, inv2]))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if 0 not in l or 1 not in l:
		print(n - 1)
	else:
		z = l.count(0)
		o = n - z
		if z - 1 - l[0:l.index(0)].count(1) > o - 1 - l[::-1][0:l[::-1].index(1)].count(0):
			l[l.index(0)] = 1
			z -= 1
		elif o - 1 > l[::-1][0:l[::-1].index(1)].count(0):
			l[n - l[::-1].index(1) - 1] = 0
			z += 1
		cz = 0
		c = 0
		for i in range(n):
			if l[i] == 1:
				c += z - cz
			else:
				cz += 1
		print(c)


def f(o):
	c1 = 0
	c2 = 0
	for i in o:
		if i == 1:
			c1 += 1
		else:
			c2 += c1
	return c2
for _ in range(int(input())):
	t = int(input())
	l = list(map(int, input().split()))
	c1 = f(l)
	p = l.copy()
	for j in range(t):
		if l[j] == 0:
			l[j] = 1
			break
	c2 = f(l)
	for j in range(t - 1, -1, -1):
		if p[j] == 1:
			p[j] = 0
			break
	c3 = f(p)
	print(max(c1, c2, c3))


def calc(a):
	ones = 0
	sum = 0
	for i in range(len(a)):
		if a[i] == '1':
			ones += 1
		else:
			sum += ones
	return sum
for _ in range(int(input())):
	n = int(input())
	s = [x for x in input().split()]
	ans = calc(s)
	for i in range(n):
		if s[i] == '0':
			s[i] = '1'
			ans = max(ans, calc(s))
			s[i] = '0'
			break
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			s[i] = '0'
			ans = max(ans, calc(s))
			s[i] = '1'
			break
	print(ans)


def get_total(data):
	curr_i = 0
	total = 0
	for i in range(len(data)):
		if data[i] == '1':
			curr_i += 1
		else:
			total += curr_i
	return total
times = int(input())
for _ in range(times):
	_ = input()
	data = input().split()
	first_zero = -1
	for i in range(len(data)):
		if data[i] == '0':
			first_zero = i
			break
	last_one = -1
	for i in range(len(data) - 1, -1, -1):
		if data[i] == '1':
			last_one = i
			break
	best = get_total(data)
	if first_zero != -1:
		data[first_zero] = '1'
		best = max(best, get_total(data))
		data[first_zero] = '0'
	if last_one != -1:
		data[last_one] = '0'
		best = max(best, get_total(data))
		data[last_one] = '1'
	print(best)


from copy import copy

def inversions(a):
	ones = 0
	ans = 0
	for i in a:
		if i:
			ones += 1
		else:
			ans += ones
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = copy(a)
	ans = inversions(a)
	for i in range(len(a)):
		if a[i] == 0:
			a[i] = 1
			break
	ans = max(ans, inversions(a))
	for i in range(len(b) - 1, -1, -1):
		if b[i] == 1:
			b[i] = 0
			break
	ans = max(ans, inversions(b))
	print(ans)


def getSum(seq, n):
	val = 0
	res = 0
	for i in range(n - 1, -1, -1):
		if seq[i] == 0:
			val += 1
		else:
			res += val
	return res

def func(seq, n):
	best = getSum(seq, n)
	i = 0
	while i < n and seq[i] == 1:
		i += 1
	if i < n:
		seq[i] = 1
		best = max(best, getSum(seq, n))
		seq[i] = 0
	i = n - 1
	while i >= 0 and seq[i] == 0:
		i -= 1
	if i >= 0:
		seq[i] = 0
		best = max(best, getSum(seq, n))
		seq[i] = 1
	return best

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		seq = list(map(int, input().split()))
		print(func(seq, n))
main()


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if len(set(l)) == 1:
		print(n - 1)
	else:
		l1 = l[::-1]
		c = 0
		inv = []
		for k in l1:
			if k == 0:
				c = c + 1
			else:
				inv.append(c)
		d = 0
		flag = 0
		for j in range(n):
			if l[j] == 1:
				d = d + 1
				flag = 1
			else:
				if flag == 0:
					ans1 = max(inv) + sum(inv) + l.index(1) - j - 1
				else:
					ans1 = max(inv) - d - flag + sum(inv)
				ans2 = sum(inv) - min(inv) + len(inv) - 1
				ans = max(ans1, ans2, sum(inv))
				break
		print(ans)


def count_inversions(a):
	ones = sum(a)
	inv = 0
	for num in a[::-1]:
		if num == 1:
			ones -= 1
		else:
			inv += ones
	return inv
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	inv1 = count_inversions(nums)
	nums2 = nums.copy()
	for i in range(n - 1, -1, -1):
		if nums2[i] == 1:
			nums2[i] = 0
			break
	inv2 = count_inversions(nums2)
	nums3 = nums.copy()
	for i in range(n):
		if nums3[i] == 0:
			nums3[i] = 1
			break
	inv3 = count_inversions(nums3)
	print(max([inv1, inv2, inv3]))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count_0 = 0
	ans = 0
	for i in range(n - 1, -1, -1):
		if a[i] == 0:
			count_0 += 1
		else:
			ans += count_0
	count_1 = 0
	change_first = ans
	change_last = ans
	for i in a:
		if i == 0:
			change_first -= count_1
			change_first += count_0 - 1
			break
		else:
			count_1 += 1
	if change_first > ans:
		ans = change_first
	count_1 = a.count(1)
	count_0 = 0
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			change_last -= count_0
			change_last += count_1 - 1
			break
		else:
			count_0 += 1
	if change_last > ans:
		ans = change_last
	print(ans)


def inversions_count(arr):
	ones = 0
	inv = 0
	for i in arr:
		if i == 1:
			ones += 1
		else:
			inv += ones
	return inv
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c1 = inversions_count(a)
	i = 0
	while a[i] == 1 and i < n - 1:
		i += 1
	a2 = a.copy()
	a2[i] = 1
	c2 = inversions_count(a2)
	i = n - 1
	while a[i] == 0 and i > 0:
		i -= 1
	a3 = a.copy()
	a3[i] = 0
	c3 = inversions_count(a3)
	print(max(c1, c2, c3))


def text(arr):
	s = 0
	m = 0
	for i in arr:
		if i == 1:
			m += 1
		else:
			s += m
	return s
for i in range(int(input())):
	input()
	ls = list(map(int, input().split()))
	lsa = ls.copy()
	s = text(ls)
	for j in range(len(ls)):
		if ls[j] == 0:
			ls[j] = 1
			break
	s = max(text(ls), s)
	for j in range(len(lsa) - 1, 0, -1):
		if lsa[j] == 1:
			lsa[j] = 0
			break
	s = max(s, text(lsa))
	print(s)


def sana(l):
	q = 0
	s = 0
	for i in range(n - 1, -1, -1):
		if l[i] == 0:
			q += 1
		else:
			s += q
	return s
for _ in int(input()) * ' ':
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	m = sana(l)
	k = l.copy()
	for i in range(n):
		if l[i] == 0:
			l[i] = 1
			break
	for i in range(n - 1, -1, -1):
		if k[i] == 1:
			k[i] = 0
			break
	print(max(sana(l), sana(k), m))


def solve():
	n = int(input())
	ls = list(map(int, input().split()))
	ro = ls.count(1)
	rz = ls.count(0)
	lo = 0
	lz = 0
	ans = 0
	c = 0
	for i in range(n):
		if ls[i] == 0:
			c += lo
			rz -= 1
			ans = max(ans, rz - lo)
			lz += 1
		else:
			ro -= 1
			ans = max(ans, lo - rz)
			lo += 1
	print(ans + c)
for i in range(int(input())):
	solve()


def kol_inv(a):
	zeros = a.count(0)
	ones = a.count(1)
	inv = 0
	for i in a:
		if i == 1:
			ones -= 1
			inv += zeros
		else:
			zeros -= 1
	return inv
t = int(input())
for i in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	inv1 = kol_inv(a)
	ind = 0
	for j in a:
		if j == 1:
			ind += 1
		else:
			break
	a1 = a.copy()
	if ind < n:
		a1[ind] = 1
	inv2 = kol_inv(a1)
	ind = n - 1
	while ind >= 0 and a[ind] == 0:
		ind -= 1
	a[ind] = 0
	inv3 = kol_inv(a)
	print(max(inv1, inv2, inv3))


def find_inversions(a):
	zeros = a.count(0)
	inversions = 0
	for num in a:
		if zeros == 0:
			break
		if num == 1:
			inversions += zeros
		else:
			zeros -= 1
	return inversions
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	max_inversions = find_inversions(arr)
	for i in range(n):
		if arr[i] == 0:
			arr[i] = 1
			max_inversions = max(max_inversions, find_inversions(arr))
			arr[i] = 0
			break
	for i in range(n - 1, -1, -1):
		if arr[i] == 1:
			arr[i] = 0
			max_inversions = max(max_inversions, find_inversions(arr))
			break
	print(max_inversions)


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	totalInv = 0
	numberOfOne = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			totalInv += numberOfOne
		else:
			numberOfOne += 1
	numberOfZero = n - numberOfOne
	oneBeforeFirstZero = 0
	for i in arr:
		if i % 2 == 0:
			break
		else:
			oneBeforeFirstZero += 1
	zeroAfterLastOne = 0
	for i in range(n - 1, -1, -1):
		if arr[i] % 2 == 1:
			break
		else:
			zeroAfterLastOne += 1
	ans1 = totalInv - oneBeforeFirstZero + (numberOfZero - 1)
	ans2 = totalInv - zeroAfterLastOne + (numberOfOne - 1)
	ans = max([totalInv, ans1, ans2])
	print(ans)


from sys import stdin, stdout

class Solution:

	def BinaryInversions(self, n, bits):
		(first, second, orig) = (bits[:], bits[:], bits[:])
		(hasFirst, hasSecond) = (True, True)
		for i in range(n):
			if hasFirst and bits[i] == 0:
				first[i] = 1
				hasFirst = False
			if hasSecond and bits[n - i - 1] == 1:
				second[n - i - 1] = 0
				hasSecond = False
		(first_sum, second_sum, orig_sum) = (0, 0, 0)
		(first_zeros, second_zeros, orig_zeros) = (0, 0, 0)
		for i in range(n - 1, -1, -1):
			if orig[i] == 0:
				orig_zeros += 1
			else:
				orig_sum += orig_zeros
			if second[i] == 0:
				second_zeros += 1
			else:
				second_sum += second_zeros
			if first[i] == 0:
				first_zeros += 1
			else:
				first_sum += first_zeros
		return max(orig_sum, first_sum, second_sum)
sol = Solution()
t = int(input())
for _ in range(t):
	n = int(input())
	bits = list(map(int, input().split()))
	print(sol.BinaryInversions(n, bits))


def f(arr):
	ind_1 = -1
	ind_0 = 9999999
	for i in range(len(arr)):
		if arr[i] == 0:
			if i < ind_0:
				ind_0 = i
		elif i > ind_1:
			ind_1 = i
	if ind_0 == 9999999 or ind_1 == -1:
		return len(arr) - 1
	k1 = 0
	k2 = 0
	k3 = 0
	k = 0
	for i in arr:
		if i == 1:
			k += 1
		else:
			k1 += k
	k = 0
	arr[ind_0] = 1
	for i in arr:
		if i == 1:
			k += 1
		else:
			k2 += k
	k = 0
	arr[ind_0] = 0
	arr[ind_1] = 0
	for i in arr:
		if i == 1:
			k += 1
		else:
			k3 += k
	return max(k1, k2, k3)
t = int(input())
for gg in range(t):
	n = int(input())
	v = [int(x) for x in input().split()]
	print(f(v))


def f(M):
	res = 0
	n = 0
	for i in range(a - 1, -1, -1):
		if M[i] == 0:
			n += 1
		else:
			res += n
	return res
t = int(input())
for _ in range(t):
	a = int(input())
	M = list(map(int, input().split()))
	M2 = [f(M)]
	for i in range(a):
		if M[i] == 0:
			M[i] = 1
			M2.append(f(M))
			M[i] = 0
			break
	for i in range(a - 1, -1, -1):
		if M[i] == 1:
			M[i] = 0
			M2.append(f(M))
			M[i] = 1
			break
	print(max(M2))


def inv_count(a):
	inv_sum = 0
	curr_inv = 0
	for x in a[::-1]:
		if x == 0:
			curr_inv += 1
		else:
			inv_sum += curr_inv
	return inv_sum
	return res

def func(a, n):
	flipone = a[:]
	flipzero = a[:]
	for i in range(n):
		if flipzero[i] == 0:
			flipzero[i] = 1
			break
	for i in range(n - 1, -1, -1):
		if flipone[i] == 1:
			flipone[i] = 0
			break
	return max(inv_count(flipone), inv_count(flipzero), inv_count(a))
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in list(input().split(' '))]
	print(func(a, n))


def countinv(l):
	inc = 0
	count = 0
	o = 0
	for i in l:
		if i == 1:
			o += 1
			inc += 1
		elif i == 0:
			count += inc
	return count
for tests in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if len(list(set(l))) == 1:
		print(n - 1)
	else:
		count1 = countinv(l)
		first0 = l.index(0)
		l[first0] = 1
		count2 = countinv(l)
		l[first0] = 0
		l.reverse()
		last1 = l.index(1)
		l[last1] = 0
		l.reverse()
		count3 = countinv(l)
		print(max([count1, count2, count3]))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = len(arr)
	c0 = c1 = nsum = sum0t1 = sum1t0 = 0
	d = {'1beforefirst0': 0, '0afterlast1': 0}
	exist0 = False
	exist1 = False
	for i in range(l - 1, -1, -1):
		if arr[i] == 0:
			c0 += 1
			exist0 = True
			d['1beforefirst0'] = 0
			if not exist1:
				d['0afterlast1'] += 1
		else:
			c1 += 1
			exist1 = True
			d['1beforefirst0'] += 1
			nsum += c0
	if exist0:
		sum0t1 = nsum - d['1beforefirst0'] + c0 - 1
	if exist1:
		sum1t0 = nsum - d['0afterlast1'] + c1 - 1
	print(max(nsum, sum0t1, sum1t0))


def solution():
	t = int(input())

	def calculate(nums):
		ans = 0
		zeroes = 0
		for i in range(len(nums) - 1, -1, -1):
			if nums[i] == 0:
				zeroes += 1
			else:
				ans += zeroes
		return ans
	for _ in range(t):
		n = int(input())
		nums = [int(x) for x in input().split()]
		ans = calculate(nums)
		for i in range(len(nums) - 1, -1, -1):
			if nums[i] == 1:
				nums[i] = 0
				ans = max(ans, calculate(nums))
				nums[i] = 1
				break
		for i in range(len(nums)):
			if nums[i] == 0:
				nums[i] = 1
				ans = max(ans, calculate(nums))
				nums[i] = 0
				break
		print(ans)
solution()


import sys
input = sys.stdin.readline

def solve():
	(N, A) = (int(input()), list(map(int, input().split())))
	ans = 0
	X = [0] * N
	t = 0
	for i in range(N - 1, -1, -1):
		if A[i] == 1:
			X[i] = t
		if A[i] == 0:
			t += 1
	ans = max(ans, sum(X))
	B = A.copy()
	for i in range(N - 1, -1, -1):
		if B[i] == 1:
			B[i] = 0
			break
	X = [0] * N
	t = 0
	for i in range(N - 1, -1, -1):
		if B[i] == 1:
			X[i] = t
		if B[i] == 0:
			t += 1
	ans = max(ans, sum(X))
	B = A.copy()
	for i in range(N):
		if B[i] == 0:
			B[i] = 1
			break
	X = [0] * N
	t = 0
	for i in range(N - 1, -1, -1):
		if B[i] == 1:
			X[i] = t
		if B[i] == 0:
			t += 1
	ans = max(ans, sum(X))
	print(ans)
for _ in range(int(input())):
	solve()


t = int(input())
for k in range(t):
	n = int(input())
	zeros = 0
	ones = 0
	res1 = 0
	res2 = 0
	res3 = 0
	l = list(map(int, input().split()))
	c = []
	aux = []
	for i in range(n):
		if l[i] == 0:
			c.append(i)
			zeros += 1
		else:
			aux.append(i)
	ones = n - zeros
	for i in range(zeros - 1, -1, -1):
		res1 += c[i] - i
	if len(c) != 0:
		res2 = res1 + zeros - 1 - c[0]
	else:
		res2 = res1
	if len(aux) != 0:
		res3 = res1 + ones - 1 - (n - aux[ones - 1] - 1)
	else:
		res3 = res1
	print(max(res1, res2, res3))


def inversion(L):
	onescount = 0
	inversioncount = 0
	for i in range(len(L)):
		if L[i] == 1:
			onescount += 1
		else:
			inversioncount = inversioncount + onescount
	return inversioncount
t = int(input())
for i in range(t):
	n = int(input())
	L1 = list(map(int, input().split()))
	(i, j) = (0, len(L1) - 1)
	L2 = L1.copy()
	L3 = L1.copy()
	while i < n:
		if L1[i] == 0:
			L2[i] = 1
			break
		i += 1
	while j >= 0:
		if L1[j] == 1:
			L3[j] = 0
			break
		j -= 1
	print(max(inversion(L1), inversion(L2), inversion(L3)))


def counter(a, n):
	mx = 0
	zeroes = 0
	for i in reversed(range(n)):
		if a[i] == 0:
			zeroes += 1
		else:
			mx += zeroes
	return mx

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = counter(a, n)
	for i in range(n):
		if a[i] == 0:
			a[i] = 1
			ans = max(ans, counter(a, n))
			a[i] = 0
			break
	for i in reversed(range(n)):
		if a[i] == 1:
			a[i] = 0
			ans = max(ans, counter(a, n))
			a[i] = 1
			break
	print(ans)
t = int(input())
while t > 0:
	solve()
	t -= 1


def solve():
	n = input()
	a = [int(x) for x in input().split(' ')]
	ct0 = 0
	ct1 = 0
	cnt = 0
	for ev in a:
		if ev == 0:
			ct0 += 1
			cnt += ct1
		else:
			ct1 += 1
	res = cnt
	be0 = 0
	be1 = 0
	for ev in a:
		ans = cnt
		if ev == 0:
			ct0 -= 1
			ans -= be1
			ans += ct0
		else:
			ct1 -= 1
			ans -= ct0
			ans += be1
		if ev == 0:
			be0 += 1
		else:
			be1 += 1
		res = max(res, ans)
	print(res)
t = int(input())
for each in range(t):
	solve()


import sys
from collections import defaultdict as dd, deque
input = lambda : sys.stdin.readline().strip()

def ii():
	return int(input())

def ia():
	return list(map(int, input().split()))
g8 = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
g4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
INF = float('inf')
MOD = 10 ** 9 + 7

def res(ar):
	s = sum(ar)
	n = len(ar)
	if n == 1:
		return 0
	ans = 0
	psum = 0
	for i in range(n - 1, -1, -1):
		psum += ar[i]
		if ar[i] == 0:
			ans += s - psum
	return ans
t = ii()
for _ in range(t):
	n = ii()
	a = ia()
	a1 = a.copy()
	ans = res(a)
	for i in range(n):
		if a[i] == 0:
			a1[i] = 1
			ans = max(ans, res(a1))
			break
	a2 = a.copy()
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			a2[i] = 0
			ans = max(ans, res(a2))
			break
	print(ans)


from copy import copy

def inversions_count(arr):
	counter = 0
	num_of_once = 0
	for item in arr:
		if item == 1:
			num_of_once += 1
		else:
			counter += num_of_once
	return counter
n = int(input())
for j in range(n):
	len_of_str = int(input())
	arr = [int(_) for _ in input().split()]
	given = inversions_count(arr)
	arr_1 = copy(arr)
	for i in range(len(arr)):
		if arr_1[i] == 0:
			arr_1[i] = 1
			break
	arr_1_count = inversions_count(arr_1)
	for i in range(len(arr) - 1, 0, -1):
		if arr[i] == 1:
			arr[i] = 0
			break
	arr_2_count = inversions_count(arr)
	result = max(given, arr_1_count)
	print(max(result, arr_2_count))


for i in range(int(input())):
	o = 0
	f = 0
	n = int(input())
	bin_list = list(map(int, input().split()))
	for j in range(n):
		if bin_list[j] == 1:
			o += 1
		else:
			f += o
	index_last_one = -1
	for j in range(n - 1, -1, -1):
		if bin_list[j] == 1:
			index_last_one = j
			break
	index_first_zero = -1
	for j in range(n):
		if bin_list[j] == 0:
			index_first_zero = j
			break
	kolvo_ones = 0
	kolvo_zeroes = 0
	for j in range(n):
		if bin_list[j] == 1:
			kolvo_ones += 1
		else:
			kolvo_zeroes += 1
	f = max(f, f + (kolvo_ones - 1) - (n - index_last_one - 1), f - index_first_zero + kolvo_zeroes - 1)
	print(f)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c1, c2) = (0, 0)
	(c3, c4) = (0, 0)
	(c5, c6) = (0, 0)
	for i in l:
		if i == 1:
			c1 += 1
		else:
			c2 += c1
	p = l.copy()
	for j in range(n):
		if l[j] == 0:
			l[j] = 1
			break
	for i in l:
		if i == 1:
			c3 += 1
		else:
			c4 += c3
	for j in range(n - 1, -1, -1):
		if p[j] == 1:
			p[j] = 0
			break
	for i in p:
		if i == 1:
			c5 += 1
		else:
			c6 += c5
	print(max(c2, c4, c6))


def cnt_inversions_in_binary_array(a):
	n = len(a)
	ans = 0
	cnt1 = 0
	for i in range(n):
		if a[i] == 0:
			ans += cnt1
		else:
			cnt1 += 1
	return ans

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	leftmost_0 = -1
	rightmost_1 = -1
	for i in range(n):
		if a[i] == 0 and leftmost_0 == -1:
			leftmost_0 = i
		elif a[i] == 1:
			rightmost_1 = i
	ans = cnt_inversions_in_binary_array(a)
	if leftmost_0 != -1:
		b = a[:]
		b[leftmost_0] = 1
		ans = max(ans, cnt_inversions_in_binary_array(b))
	if rightmost_1 != -1:
		b = a[:]
		b[rightmost_1] = 0
		ans = max(ans, cnt_inversions_in_binary_array(b))
	print(ans)
N = int(input())
for _ in range(N):
	solve()


import collections
import itertools
import heapq
import sys
import math
import bisect
import os
from io import BytesIO, IOBase
input = sys.stdin.readline

def get(ll):
	tot = 0
	o = 0
	for i in ll:
		if i == 1:
			o += 1
		else:
			tot += o
	return tot

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	c = collections.Counter(l)
	if 0 not in c:
		n - 1
	if 1 not in c:
		n - 1
	z = 0
	o = 0
	g = get(l)
	mx = g
	for i in range(n):
		if l[i] == 0:
			z += 1
		if l[i] == 0:
			mx = max(mx, g - o + c[0] - z)
		elif l[i] == 1:
			mx = max(mx, g - (c[0] - z) + o)
		if l[i] == 1:
			o += 1
	return mx
for i in range(int(input())):
	print(solve())


import collections
import sys
import os
input = sys.stdin.readline

def get(ll):
	tot = 0
	o = 0
	for i in ll:
		if i == 1:
			o += 1
		else:
			tot += o
	return tot

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	c = collections.Counter(l)
	if 0 not in c:
		return n - 1
	if 1 not in c:
		return n - 1
	z = 0
	o = 0
	g = get(l)
	mx = g
	for i in range(n):
		if l[i] == 0:
			z += 1
		if l[i] == 0:
			mx = max(mx, g - o + c[0] - z)
		elif l[i] == 1:
			mx = max(mx, g - (c[0] - z) + o)
		if l[i] == 1:
			o += 1
	return mx
for i in range(int(input())):
	print(solve())


def inversion(a):
	count = 0
	ans = 0
	for i in range(len(a) - 1, -1, -1):
		if a[i] == 0:
			count += 1
		else:
			ans += count
	return ans
t = int(input())
while t > 0:
	n = int(input())
	a = [int(c) for c in input().split()]
	ans1 = inversion(a)
	b = a[:]
	for i in range(0, len(b)):
		if b[i] == 0:
			b[i] = 1
			break
	ans2 = inversion(b)
	for i in range(len(a) - 1, 0, -1):
		if a[i] == 1:
			a[i] = 0
			break
	ans3 = inversion(a)
	print(max(max(ans1, ans2), ans3))
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	b = a.copy()
	sums = 0
	sums0 = a.count(0)
	sums1 = a.count(1)
	p0 = 0
	p1 = 0
	for i in range(n - 1):
		if a[i] == 0:
			p0 += 1
		if a[i] == 1:
			sums += sums0 - p0
	(p0, p0) = (0, 0)
	sumss = 0
	for i in range(n):
		if a[i] == 1:
			p1 += 1
		if a[i] == 0:
			sumss = max(sumss, sums0 - p0 - 1 - p1)
			break
	(p0, p1) = (0, 0)
	for i in range(n - 1, -1, -1):
		if a[i] == 0:
			p0 += 1
		if a[i] == 1:
			sumss = max(sumss, sums1 - 1 - p0)
			break
	print(max(sums, sumss + sums))


for s in [*open(0)][2::2]:
	k = l = m = 0
	c = s.count('1')
	n = len(s) // 2
	for x in map(int, s[::2]):
		n -= 1
		k += x
		m = max(m, (n - c, c - n - 1)[x])
		l += (x ^ 1) * k
	print(l + m)


def solve():
	t = int(input())
	while t:
		n = int(input())
		arr = list(map(int, input().split()))
		temp = []
		for i in arr:
			temp.append(i)
		(res, c) = (0, 0)
		for i in range(n - 1, -1, -1):
			if arr[i] == 1:
				res += c
			else:
				c += 1
		for i in range(n - 1, -1, -1):
			if arr[i] == 1:
				arr[i] = 0
				break
		for i in range(n):
			if temp[i] == 0:
				temp[i] = 1
				break
		(ans, res1) = (0, 0)
		(count, count2) = (0, 0)
		for i in range(n - 1, -1, -1):
			if arr[i] == 1:
				ans += count
			elif arr[i] == 0:
				count += 1
			if temp[i] == 1:
				res1 += count2
			elif temp[i] == 0:
				count2 += 1
		print(max(res, max(res1, ans)))
		t -= 1
solve()


def count(l):
	c = l.count(0)
	ans = 0
	for i in range(n):
		if l[i] == 1:
			ans = ans + c
		elif l[i] == 0:
			c = c - 1
	return ans
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = y = z = 0
	z = count(l)
	for i in range(n):
		if l[i] == 0:
			l[i] = 1
			x = count(l)
			l[i] = 0
			break
	for i in range(n):
		if l[-i - 1] == 1:
			l[-i - 1] = 0
			y = count(l)
			l[-i - 1] = 0
			break
	print(max(x, y, z))


def counts(num):
	c0 = 0
	ans = 0
	for i in range(len(num) - 1, -1, -1):
		if num[i] == 0:
			c0 += 1
		else:
			ans += c0
	return ans
for i in range(int(input())):
	length = int(input())
	num = [int(x) for x in input().split()]
	last_one = length - 1
	first_zero = 0
	for i in range(length):
		if num[i] == 0:
			first_zero = i
			break
	for i in range(length - 1, -1, -1):
		if num[i] == 1:
			last_one = i
			break
	ori = counts(num)
	temp = num.copy()
	temp[last_one] = 0
	oneToZero = counts(temp)
	num[first_zero] = 1
	zeroToOne = counts(num)
	print(max(ori, oneToZero, zeroToOne))


def check_inversion(n, arr):
	ans = 0
	one = 0
	for i in range(n):
		if arr[i] == 1:
			one += 1
		elif arr[i] == 0:
			ans += one
	return ans
for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	lst = []
	lst.append(check_inversion(a, b))
	check = -1
	for i in range(a):
		if b[i] == 0:
			b[i] = 1
			check = i
			lst.append(check_inversion(a, b))
			break
	if check != -1:
		b[check] = 0
	for i in range(a - 1, 0, -1):
		if b[i] == 1:
			b[i] = 0
			lst.append(check_inversion(a, b))
			break
	print(max(lst))


for t in range(int(input())):
	N = int(input())
	arr = input().split()
	arrFwd = list(arr)
	arrBwd = list(arr)

	def count(arr):
		(totalK, ones, cur0) = (0, 0, 0)
		for i in range(N + 1):
			if arr[i] == '1':
				totalK += cur0 * ones
				cur0 = 0
				ones += 1
			else:
				cur0 += 1
		return totalK
	arr.append('1')
	T0 = count(arr)
	for i in range(N):
		if arrFwd[i] == '0':
			arrFwd[i] = '1'
			break
	arrFwd.append('1')
	T1 = count(arrFwd)
	for i in range(N - 1, -1, -1):
		if arrBwd[i] == '1':
			arrBwd[i] = '0'
			break
	arrBwd.append('1')
	T2 = count(arrBwd)
	print(max(T0, T1, T2))


import sys

def read(func=int):
	return func(sys.stdin.readline().strip())

def read_array(func=int):
	return list(map(func, read(str).split()))
t = read()
for _ in range(t):
	n = read()
	A = read_array()
	ones = [0] * n
	fst0 = float('inf')
	ltr1 = -1
	ans = 0
	for i in range(n):
		ones[i] = A[i] + ones[i - 1]
		if A[i]:
			ltr1 = max(ltr1, i)
		else:
			fst0 = min(fst0, i)
			ans += ones[i - 1]
	ansG = ans
	if fst0 < float('inf'):
		ones_left = ones[fst0]
		ones_right = ones[-1] - ones[fst0]
		nums_right = n - fst0 - 1
		zeros_right = nums_right - ones_right
		ansG = max(ansG, ans + zeros_right - ones_left)
	if ltr1 != -1:
		ones_left = ones[ltr1] - 1
		ones_right = ones[-1] - ones[i]
		nums_right = n - ltr1 - 1
		zeros_right = nums_right - ones_right
		ansG = max(ansG, ans + ones_left - zeros_right)
	print(ansG)


t = int(input())
while t:
	l = int(input())
	s = list(map(int, input().split()))

	def calc(arr):
		z = 0
		ans = 0
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] == 0:
				z = z + 1
			else:
				ans += z
		return ans
	ini = calc(s)
	case1 = s.copy()
	case2 = s.copy()
	for i in range(l - 1, -1, -1):
		if case1[i] == 1:
			case1[i] = 0
			break
	for i in range(l):
		if case2[i] == 0:
			case2[i] = 1
			break
	print(max([ini, calc(case1), calc(case2)]))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if 0 not in a or 1 not in a:
		print(n - 1)
		continue
	ind0 = a.index(0)
	ind1 = 0
	for i in range(n):
		if a[i] == 1:
			ind1 = i
	m = a[:ind0].count(1)
	k = a[ind0:].count(0) - 1
	flag = False
	if (m + 1) * k > m * (k + 1):
		a[ind0] = 1
		flag = True
	l = a.count(0)
	count = 0
	for i in a:
		if i:
			count += l
		else:
			l -= 1
	if flag:
		a[ind0] = 0
	m = a[:ind1].count(1)
	k = a[ind1:].count(0)
	if (m + 1) * k < m * (k + 1):
		a[ind1] = 0
	l = a.count(0)
	count2 = 0
	for i in a:
		if i:
			count2 += l
		else:
			l -= 1
	print(max(count, count2))


import sys
import os
import math
from collections import defaultdict
from collections import Counter
from collections import deque
from heapq import heappush, heappop

def cnt_inversions_in_binary_array(a):
	n = len(a)
	ans = 0
	cnt1 = 0
	for i in range(n):
		if a[i] == 0:
			ans += cnt1
		else:
			cnt1 += 1
	return ans

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	leftmost_0 = -1
	rightmost_1 = -1
	for i in range(n):
		if a[i] == 0 and leftmost_0 == -1:
			leftmost_0 = i
		elif a[i] == 1:
			rightmost_1 = i
	ans = cnt_inversions_in_binary_array(a)
	if leftmost_0 != -1:
		b = a[:]
		b[leftmost_0] = 1
		ans = max(ans, cnt_inversions_in_binary_array(b))
	if rightmost_1 != -1:
		b = a[:]
		b[rightmost_1] = 0
		ans = max(ans, cnt_inversions_in_binary_array(b))
	print(ans)

def main():
	N = int(input())
	for _ in range(N):
		solve()
main()


def op1(l):
	l2 = []
	for i in l:
		l2.append(i)
	for i in range(len(l2)):
		if l2[i] == 0:
			l2[i] = 1
			break
	return l2

def op2(l, m):
	l2 = []
	for i in l:
		l2.append(i)
	for i in range(m - 1, -1, -1):
		if l2[i] == 1:
			l2[i] = 0
			break
	return l2

def count(l2):
	c = 0
	s = 0
	for i in l2:
		if i == 1:
			c += 1
		else:
			s += c
	return s
t = int(input())
for i in range(t):
	n = int(input())
	k = list(map(int, input().split(' ')))
	c1 = count(k)
	k1 = op1(k)
	c2 = count(k1)
	k2 = op2(k, n)
	c3 = count(k2)
	print(max(c1, c2, c3))


t = int(input())
for i in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	s2 = s[:]
	count = 0
	ans = 0
	for x in s:
		if x == 1:
			count += 1
		else:
			ans += count
	idx = 0
	for i in range(len(s2) - 1, -1, -1):
		if s2[i] == 1:
			s2[i] = 0
			break
	count1 = ans1 = 0
	for x in s2:
		if x == 1:
			count1 += 1
		else:
			ans1 += count1
	for i in range(len(s)):
		if s[i] == 0:
			s[i] = 1
			break
	count2 = ans2 = 0
	for x in s:
		if x == 1:
			count2 += 1
		else:
			ans2 += count2
	print(max(ans1, ans2, ans))


def solve(myArr):
	ans = 0
	zeros = 0
	for i in myArr[::-1]:
		zeros += 1 - i
		ans += i * zeros
	return ans
for _ in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	arr2 = arr.copy()
	if 0 in arr2:
		arr2[arr2.index(0)] = 1
	arr1 = arr[::-1].copy()
	if 1 in arr1:
		arr1[arr1.index(1)] = 0
		arr1 = arr1[::-1]
	print(max(solve(arr), solve(arr2), solve(arr1)))


def inversion(string: list):
	count = 0
	count0 = string.count('0')
	count1 = string.count('1')
	for i in range(len(string)):
		if string[i] == '1':
			count1 -= 1
			count += count0
		else:
			count0 -= 1
	return count

def oi():
	a = input().split()
	if '0' not in a or '1' not in a:
		return len(a) - 1
	first_zero = a.index('0')
	a.reverse()
	last_one = len(a) - a.index('1') - 1
	a.reverse()
	h1 = inversion(a)
	h2 = inversion(a[:first_zero] + ['1'] + a[first_zero + 1:])
	h3 = inversion(a[:last_one] + ['0'] + a[last_one + 1:])
	return max(h1, h2, h3)
for i in range(int(input())):
	input()
	print(oi())


t = int(input())
for i in range(t):
	n = int(input())
	barray = list(map(int, input().split()))
	veryfirst0 = 0
	verylast1 = 0
	first0found = False
	first1found = False
	for i in range(n):
		if barray[i] == 0 and (not first0found):
			first0found = True
			veryfirst0 = barray[i + 1:].count(0) - i
			barrayinv0 = barray[:i] + [1] + barray[i + 1:]
		if barray[n - 1 - i] == 1 and (not first1found):
			first1found = True
			verylast1 = barray[:n - 1 - i].count(1) - i
			barrayinv1 = barray[:n - 1 - i] + [0] + barray[n - i:]
		if first0found and first1found:
			break
	if veryfirst0 >= verylast1 and veryfirst0 > 0:
		barray = barrayinv0
	elif verylast1 > veryfirst0 and verylast1 > 0:
		barray = barrayinv1
	index1 = []
	for i in range(n):
		if barray[i] == 1:
			index1.append(i)
	noinv = 0
	no1 = len(index1)
	for i in range(len(index1)):
		no0after1 = n - 1 - index1[i] - (no1 - 1 - i)
		noinv += no0after1
	print(noinv)


import math
from collections import Counter

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

def n():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L

def inL0(size):
	L = [0 for i in range(size)]
	return L

def process(L):
	z = L.count(0)
	o = size - z
	ans = 0
	for i in range(size):
		if L[i] == 0:
			z -= 1
		else:
			ans += z
	return ans
for _ in range(int(input())):
	size = n()
	L = li()
	z = L.count(0)
	o = size - z
	if z == 0 or o == 0:
		print(size - 1)
		continue
	ultiL = list(L)
	ultiL = ultiL[::-1]
	pos0 = L.index(0)
	pos1 = ultiL.index(1)
	check1 = list(L)
	check2 = list(L)
	check1[pos0] = 1
	check2[-pos1 - 1] = 0
	ans = process(L)
	temp1 = process(check1)
	temp2 = process(check2)
	print(max(ans, temp1, temp2))


for j in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	start = 0
	st = 0
	nst = 0
	end = 0
	en = 0
	nen = 0
	zero = 0
	one = 0
	res = 0
	for i in a:
		if i == 0:
			if start == 1:
				st += 1
			if start == 0:
				start = 1
				nst = one
			zero += 1
			res += one
		else:
			one += 1
	zero = 0
	one = 0
	for i in a[::-1]:
		if i == 0:
			zero += 1
		else:
			if end == 1:
				en += 1
			if end == 0:
				end = 1
				nen = zero
			one += 1
			one += 1
	print(max(res, res - nst + st, res - nen + en))


def evaluate(arr) -> int:
	s = k = 0
	for i in range(len(arr)):
		if arr[i]:
			k += 1
		else:
			s += k
	return s
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = evaluate(arr)
	p = arr.copy()
	if 0 in p:
		p[p.index(0)] = 1
		ans = max(ans, evaluate(p))
	p = arr.copy()
	if 1 in p:
		p[n - list(reversed(p)).index(1) - 1] = 0
		ans = max(ans, evaluate(p))
	print(ans)


def get_inv(arr, n):
	count = 0
	zeros = arr.count(0)
	for i in arr:
		if i == 1:
			count += zeros
		else:
			zeros -= 1
	return count

def solve(arr, n):
	ones = arr.count(1)
	zeros = n - ones
	l_zeros = 0
	l_ones = 0
	r_zeros = zeros
	r_ones = ones
	maxx = -10 ** 9
	for i in range(n):
		if arr[i] == 1:
			l_ones += 1
			r_ones -= 1
			maxx = max(maxx, l_ones - r_zeros - 1)
		else:
			l_zeros += 1
			r_zeros -= 1
			maxx = max(maxx, r_zeros - l_ones)
	return maxx
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	a = get_inv(arr, n)
	b = solve(arr, n)
	print(max(a + b, a))


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	b.reverse()
	k0 = 0
	col = 0
	m = []
	for i in b:
		if i == 0:
			col += 1
		elif i == 1:
			m.append(col)
	c = []
	(k0, k1) = (0, 0)
	for i in b:
		if i == 0:
			c.append(-(len(m) - k1) + k0)
			k0 += 1
		else:
			k1 += 1
			c.append(len(m) - k1 - k0)
	print(max(sum(m), sum(m) + max(c)))


def check(arr):
	a = 0
	ans = 0
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] == 0:
			a += 1
		else:
			ans += a
	return ans

def solve():
	n = int(input())
	s = list(map(int, input().split()))
	init = check(s)
	cas1 = s.copy()
	cas2 = s.copy()
	for i in range(n - 1, -1, -1):
		if cas1[i] == 1:
			cas1[i] = 0
			break
	for i in range(n):
		if cas2[i] == 0:
			cas2[i] = 1
			break
	return max(init, check(cas1), check(cas2))
for t in range(0, int(input())):
	print(solve())


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	ans = 0
	one = l.count(1)
	zero = l.count(0)
	for j in range(n - 1, -1, -1):
		if l[j] == 0:
			count += 1
		else:
			ans += count
	rone = 0
	for j in l:
		if j == 1:
			rone += 1
		else:
			break
	ans1 = zero - rone - 1
	l.reverse()
	lzero = 0
	for j in l:
		if j == 0:
			lzero += 1
		else:
			break
	ans2 = one - lzero - 1
	print(max(ans, ans + ans1, ans + ans2))


import sys
input = sys.stdin.readline

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

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

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

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	num = inp()
	nums = inlt()
	inp_arr.append(nums)

def cal(nums):
	c_one = sum(nums)
	result = 0
	for (i, n) in enumerate(nums):
		if n == 1:
			result += len(nums) - i - 1 - c_one + 1
			c_one -= 1
	return result

def findResult(nums):
	result = cal(nums)
	zero_index = -1
	for i in range(len(nums)):
		if nums[i] == 0:
			zero_index = i
			break
	if zero_index != -1:
		nums[zero_index] = 1
		result = max(result, cal(nums))
		nums[zero_index] = 0
	one_index = -1
	for i in range(len(nums) - 1, -1, -1):
		if nums[i] == 1:
			one_index = i
			break
	if one_index != -1:
		nums[one_index] = 0
		result = max(result, cal(nums))
	return result
result = [findResult(cheeses) for cheeses in inp_arr]
for m in result:
	print(m)


t = int(input())

def cou(arr):
	k = 0
	ans = 0
	for i in arr:
		if i == 1:
			k += 1
		elif i == 0:
			ans += k
	return ans
while t > 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	b = []
	for i in l:
		a.append(i)
		b.append(i)
	for i in range(n):
		if a[i] == 0:
			a[i] = 1
			break
	for i in range(n - 1, -1, -1):
		if b[i] == 1:
			b[i] = 0
			break
	print(max(cou(l), max(cou(a), cou(b))))