You have an array $a$ of size $n$ consisting only of zeroes and ones. You can do the following operation:

choose two indices $1 \le i , j \le n$, $i \ne j$,

add $a_{i}$ to $a_{j}$,

remove $a_{i}$ from $a$.

Note that elements of $a$ can become bigger than $1$ after performing some operations. Also note that $n$ becomes $1$ less after the operation.

What is the minimum number of operations needed to make $a$ non-decreasing, i. e. that each element is not less than the previous element?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$), the size of array $a$.

Next line contains $n$ integers $a_{1}, a_{2}, \ldots a_{n}$ ($a_i$ is $0$ or $1$), elements of array $a$.

It's guaranteed that sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case print a single integer, minimum number of operations needed to make $a$ non-decreasing.


-----Examples-----

Input
4
8
0 0 1 1 1 1 1 1
5
1 0 0 1 1
2
1 0
11
1 1 0 0 1 0 0 1 1 1 0
Output
0
1
1
3


-----Note-----

In the first test case, $a$ is already non-decreasing, so you don't need to do any operations and the answer is $0$.

In the second test case, you can perform an operation for $i = 1$ and $j = 5$, so $a$ will be equal to $[0, 0, 1, 2]$ and it becomes non-decreasing.

In the third test case, you can perform an operation for $i = 2$ and $j = 1$, so $a$ will be equal to $[1]$ and it becomes non-decreasing.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Amortized analysis

Constructive algorithms


Solutions:
for s in [*open(0)][2::2]:
	print(s[:s.count('0') * 2].count('1'))


for l in [*open(0)][2::2]:
	print(l[:l.count('0') * 2].count('1'))


for q in [*open(0)][2::2]:
	print(q[:q.count('0') * 2].count('1'))


for j in [*open(0)][2::2]:
	print(j[:j.count('0') * 2].count('1'))


for a in [*open(0)][2::2]:
	print(a[:a.count('0') * 2].count('1'))


for t in [*open(0)][2::2]:
	print(t[:t.count('0') * 2].count('1'))


for sa in [*open(0)][2::2]:
	print(sa[:sa.count('0') * 2].count('1'))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	a = input().split()
	print(a[:a.count('0')].count('1'))


for x in [*open(0)][2::2]:
	print(x[:x.count('0') * 2].count('1'))


for k in [*open(0)][2::2]:
	print(k[:k.count('0') * 2].count('1'))


for s in [*open(0)][2::2]:
	k = s.count('0') * 2
	print(max(s[:k].count('1'), s[k:].count('0')))


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnt0 = l.count(0)
	c = l[:cnt0]
	print(c.count(1))


import sys

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		arr = list(map(int, sys.stdin.readline().split()))
		_chg = 0
		(i, j) = (0, N - 1)
		while i < j:
			while i < N and arr[i] == 0:
				i += 1
			while j >= 0 and arr[j] == 1:
				j -= 1
			if i < j:
				_chg += 1
			i += 1
			j -= 1
		print(_chg)
main()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	(f, b) = (0, n - 1)
	ans = 0
	while f < b:
		if arr[f] == 0:
			f += 1
		else:
			while f < b and arr[b] == 1:
				b -= 1
			if f < b:
				ans += 1
				arr[b] = 1
				f += 1
	return ans
for _ in range(int(input())):
	print(solve())


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	cnt = 0
	ones = sum(a)
	zeros = n - ones
	for i in range(n):
		if zeros <= 0:
			break
		if a[i] == 1:
			ones -= 1
			zeros -= 1
			cnt += 1
		else:
			zeros -= 1
	print(cnt)


for s in [*open(0)][2::2]:
	l = [*map(int, s.split())]
	(a, b) = (l.count(0), l.count(1))
	ans = 0
	for x in l:
		if a <= 0:
			break
		a -= 1
		if x:
			ans += 1
	print(ans)


def min_number(ls):
	return sum(ls[:len(ls) - sum(ls)])
n = int(input())
answer = []
for i in range(n):
	a = input()
	ls = list(map(int, input().split()))
	answer.append(min_number(ls))
for i in answer:
	print(i)


import sys
input = sys.stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		(i, j) = (0, n - 1)
		sol = 0
		while i < j:
			if a[j] == 0 and a[i] == 1:
				sol += 1
				i += 1
				j -= 1
			elif a[j] == 0:
				i += 1
			elif a[i] == 1:
				j -= 1
			else:
				i += 1
				j -= 1
		print(sol)
main()


import sys
import sys, threading
from heapq import heapify, heappop, heappush
from math import log10, floor, pow, gcd, sqrt, inf, log2, ceil
from collections import defaultdict, deque, Counter
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())

def main():
	tests = inp()
	for _ in range(tests):
		n = inp()
		a = inlt()
		left = 0
		right = n - 1
		count = 0
		while left < right:
			while right > left and a[right] != 0:
				right -= 1
			while left < right and a[left] != 1:
				left += 1
			if left < right:
				count += 1
				left += 1
				right -= 1
		print(count)
main()


fl = 'input.txt'
import sys
import math
flh = sys.stdin
test_cases = int(flh.readline())
res = []
for case in range(test_cases):
	n = int(flh.readline())
	a = [int(x) for x in flh.readline().strip().split()]
	s = n - sum(a)
	print(sum(a[:s]))


import io
import sys

def calculate(n: int, a: list) -> int:
	left = 0
	right = n - 1
	steps = 0
	while left < right:
		if a[right] != 0:
			right -= 1
			continue
		if a[left] != 1:
			left += 1
			continue
		a[right] += a[left]
		left += 1
		steps += 1
	return steps

def main():
	t = int(sys.stdin.readline())
	for i in range(t):
		n = int(sys.stdin.readline())
		a = list(map(int, sys.stdin.readline().split()))
		print(calculate(n, a))
main()


import sys
num_of_cases = int(sys.stdin.readline().rstrip())
for _ in range(num_of_cases):
	ans = 0
	total_num = int(sys.stdin.readline().rstrip())
	nums = sys.stdin.readline().rstrip().split()
	i = 0
	j = total_num - 1
	while i < j:
		if nums[i] == '1' and nums[j] == '0':
			ans += 1
			i += 1
			j -= 1
		else:
			if nums[i] == '0':
				i += 1
			if nums[j] == '1':
				j -= 1
	print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	f = 0
	k = 0
	c = l.count(1)
	for i in range(len(l) - 1, len(l) - c - 1, -1):
		if l[i] == 0:
			k += 1
	print(k)


def Rebel(arr):
	n = arr.count(1)
	rev = arr[::-1]
	ans = 0
	for i in range(0, n):
		x = rev[i]
		if x != 1:
			ans += 1
	return ans
OUTPUT = []
for _ in range(int(input())):
	N = int(input())
	arr = [int(x) for x in input().split()]
	OUTPUT.append(Rebel(arr))
for _ in OUTPUT:
	print(_)


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())
n = inp()

def solution(a):
	(i, j) = (0, len(a) - 1)
	res = 0
	while i < j:
		while i < len(a) and a[i] == 0:
			i += 1
		while j >= 0 and a[j] == 1:
			j -= 1
		if i < j:
			res += 1
		i += 1
		j -= 1
	print(res)
for i in range(n):
	len_a = inp()
	a = inlt()
	solution(a)


testcases = []
for i in range(int(input())):
	input()
	testcases.append(input().split(' '))
for tc in testcases:
	s = sorted(tc)
	count = 0
	for i in range(len(s)):
		if s[i] != tc[i]:
			count += 1
	print(int(count / 2))


n = int(input())
i = 0
while i < n:
	x = int(input())
	t = input().split()
	print(t[:t.count('0')].count('1'))
	i += 1


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	i = 0
	j = n - 1
	while i < j:
		if l[i] == 0:
			i += 1
		elif l[j] == 0:
			ans += 1
			i += 1
			j -= 1
		else:
			j -= 1
	print(ans)


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	n = int(sys.stdin.readline().strip())
	a = list(map(int, sys.stdin.readline().strip().split()))
	i = 0
	j = n - 1
	ans = 0
	while i < j:
		if a[i] == 0:
			i += 1
		elif a[j] == 1:
			j -= 1
		else:
			ans += 1
			i += 1
			j -= 1
	print(ans)


from sys import stdin
t = int(stdin.readline().strip())
for i in range(t):
	n = int(stdin.readline().strip())
	a = list(map(str, stdin.readline().split()))
	a2 = sorted(a)
	a3 = 0
	for i in range(n):
		if a[i] != a2[i]:
			a3 += 1
	print(a3 // 2)


n = int(input())
answer = []
for i in range(n):
	x = input()
	a = input().split()
	x = sorted(a)
	moves = 0
	for i in range(0, len(a)):
		if a[i] != x[i]:
			moves += 0.5
	answer.append(round(moves))
for i in answer:
	print(i)


import sys
input = sys.stdin.readline
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	cnt = 0
	if l == l1:
		cnt = 0
	for i in range(len(l)):
		if l[i] != l1[i]:
			cnt += 1
	print(cnt // 2)


t = int(input())
a = [0] * t
b = []
c = []
for i in range(t):
	k = int(input())
	b.append(k)
	a[i] = [int(j) for j in input().split()]
s = 0
for i in range(t):
	c = a[i]
	if c.count(0) == 0 or c.count(1) == 0:
		print(0)
		continue
	l = c.count(0)
	d = c[:l]
	print(d.count(1))


for i in range(int(input())):
	n = int(input())
	L = input().split()
	c = 0
	for i in range(n - 1, n - L.count('1') - 1, -1):
		if L[i] == '0':
			c += 1
	print(c)


t = int(input())
sp = []
sm = []
for i in range(t):
	n = int(input())
	ab = input()
	ab = ab.split()
	sm.append([int(x) for x in ab])
for i in range(t):
	b = sm[i].copy()
	b.sort()
	if 1 in b:
		ind_1 = b.index(1)
	else:
		print(0)
		continue
	b = sm[i].copy()
	print(b[:ind_1].count(1))


t = int(input())
for i in range(t):
	n = int(input())
	lst = input().split()
	Operation1 = lst.count('0')
	n1 = lst.count('1')
	n1_ = lst[n - n1:n + 1].count('1')
	Operation2 = n1 - n1_
	print(min(Operation2, Operation1))


import math
import sys
from collections import deque, OrderedDict, defaultdict
import heapq, re
from collections import Counter

def inp():
	return sys.stdin.readline().rstrip()

def mpp():
	return map(int, inp().split())

def lis():
	return list(mpp())

def yn(n):
	if n:
		return 'YES'
	else:
		return 'NO'

def cd(s):
	return ord(s) - ord('a') + 1
prime = [True for i in range(10000)]

def sieve(n):
	p = 2
	prime[1] = False
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1

def hcf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def fn(arr, n):
	c = sorted(arr)
	if arr == c:
		return 0
	cn = 0
	for i in range(n):
		if arr[i] != c[i]:
			cn += 1
	return cn // 2

def main():
	t = int(inp())
	for _ in range(t):
		n = int(inp())
		arr = lis()
		print(fn(arr, n))
main()


import sys
input = sys.stdin.readline
for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	i = 0
	j = n - 1
	while i < j:
		while i < j and a[i] != 1:
			i += 1
		while i < j and a[j] != 0:
			j -= 1
		if i < j:
			c += 1
			i += 1
			j -= 1
	print(c)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	j = n - 1
	i = 0
	ans = 0
	while True:
		while j >= 0 and a[j] > 0:
			j -= 1
		while i < n and a[i] == 0:
			i += 1
		if j < i:
			break
		a[i] -= 1
		a[j] += 1
		ans += 1
	print(ans)

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


def solve():
	n = int(input())
	a = input().replace(' ', '')
	j = n - 1
	cnt = i = 0
	while i < j:
		while i < j and a[i] == '0':
			i += 1
		while i < j and a[j] == '1':
			j -= 1
		if i < j:
			cnt += 1
			i += 1
			j -= 1
	print(cnt)
for i in range(int(input())):
	solve()


from sys import stdin

def read():
	return stdin.readline().strip()
for _ in range(int(read())):
	n = int(read())
	arr = list(map(int, read().split(' ')))
	s = 0
	i = 0
	j = len(arr) - 1
	while i < j:
		if arr[i] == 0:
			i += 1
		elif arr[j] == 1:
			j -= 1
		else:
			s += 1
			i += 1
			arr[j] = 1
	print(s)


n = int(input())
lst_ans = []
for i in range(n):
	len_1 = int(input())
	list01 = list(map(int, input().split()))
	j = len_1 - 1
	i = 0
	count_1 = 0
	while True:
		if i <= j:
			if list01[j] == 0:
				if list01[i] == 1:
					(list01[j], list01[i]) = (list01[i], list01[j])
					count_1 += 1
					j = j - 1
				i += 1
			else:
				j = j - 1
		else:
			break
	lst_ans.append(count_1)
for g in lst_ans:
	print(g)


def check(m):
	if str(m) == str(sorted(m)):
		return 1
	else:
		return 0
t = int(input())
for i in range(t):
	n = input()
	m = list(map(int, input().split()))
	ans = 0
	num = m.count(1)
	m1 = m[len(m) - num:]
	print(m1.count(0))


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	array = list(map(int, sys.stdin.readline().split()))
	reverseArray = sorted(array)
	if array == reverseArray:
		print(0)
		continue
	operationCount = 0
	ptr1 = 0
	ptr2 = n - 1
	while ptr2 > ptr1:
		if array[ptr2] != 0:
			ptr2 -= 1
			continue
		if array[ptr1] != 1:
			ptr1 += 1
			continue
		if ptr2 > ptr1:
			array[ptr2] = 1
			operationCount += 1
			ptr2 -= 1
			ptr1 += 1
	print(operationCount)
	continue


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.count(0)
	print(l[:a].count(1))


t = int(input())
tcount = []
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	i = 0
	j = n - 1
	count = 0
	while i < j:
		while i < n and A[i] != 1:
			i += 1
		while j >= 0 and A[j] != 0:
			j -= 1
		if i > j:
			break
		A[j] += A[i]
		A[i] = 0
		i += 1
		j -= 1
		count += 1
	tcount.append(count)
print(*tcount, sep='\n')


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	one = sum(lst)
	print(one - sum(lst[n - one:]))


from sys import stdin
from collections import Counter

def readint():
	return int(stdin.readline())

def readarray(typ):
	return list(map(typ, stdin.readline().split()))
t = readint()
for _ in range(t):
	n = readint()
	A = readarray(int)
	c_whole = Counter(A)
	final_index = n - c_whole[1]
	c_partial = Counter(A[:final_index])
	print(c_partial[1])


a = int(input())
sp = []
for i in range(a):
	j = int(input())
	n = list(map(int, input().split()))
	x = sorted(n)
	k = 0
	for t in range(j):
		if x[t] != n[t]:
			k += 1
	sp.append(k // 2)
for y in sp:
	print(y)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	x = sum(lst)
	print(x - sum(lst[-x:]))


for _ in range(int(input())):
	total = int(input())
	k = list(map(int, input().split()))
	print(sum(k[0:total - sum(k)]))


t = int(input())
l = []
for i in range(t):
	size = int(input())
	a = list(map(int, input().split()))
	x = sorted(a)
	k = 0
	for i in range(size):
		if x[i] != a[i]:
			k += 1
	l.append(k // 2)
for i in l:
	print(i)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	print(sum(a[:n - total]))


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(sum(arr[:n - sum(arr)]))


t = int(input())
num_swap = []
for i in range(1, t + 1):
	n = int(input())
	arr = list(map(int, input().split()))
	one_ptr = 0
	zero_ptr = n - 1
	swaps = 0
	while one_ptr < zero_ptr:
		if arr[one_ptr] == 1 and arr[zero_ptr] == 0:
			one_ptr += 1
			zero_ptr -= 1
			swaps += 1
		if arr[one_ptr] != 1:
			one_ptr += 1
		if arr[zero_ptr] != 0:
			zero_ptr -= 1
	num_swap.append(swaps)
for i in range(len(num_swap)):
	print(num_swap[i])


for _ in range(int(input())):
	j = int(input())
	list1 = list(map(int, input().split()))
	print(list1[:list1.count(0)].count(1))