Mark is cleaning a row of $n$ rooms. The $i$-th room has a nonnegative dust level $a_i$. He has a magical cleaning machine that can do the following three-step operation.

Select two indices $i<j$ such that the dust levels $a_i$, $a_{i+1}$, $\dots$, $a_{j-1}$ are all strictly greater than $0$.

Set $a_i$ to $a_i-1$.

Set $a_j$ to $a_j+1$.

Mark's goal is to make $a_1 = a_2 = \ldots = a_{n-1} = 0$ so that he can nicely sweep the $n$-th room. Determine the minimum number of operations needed to reach his goal.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2\leq n\leq 2\cdot 10^5$) — the number of rooms.

The second line of each test case contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($0\leq a_i\leq 10^9$) — the dust level of each room.

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


-----Output-----

For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.


-----Examples-----

Input
4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10
Output
3
5
11
0


-----Note-----

In the first case, one possible sequence of operations is as follows.

Choose $i=1$ and $j=2$, yielding the array $[1,1,0]$.

Choose $i=1$ and $j=3$, yielding the array $[0,1,1]$.

Choose $i=2$ and $j=3$, yielding the array $[0,0,2]$.

At this point, $a_1=a_2=0$, completing the process.

In the second case, one possible sequence of operations is as follows.

Choose $i=4$ and $j=5$, yielding the array $[0,2,0,1,1]$.

Choose $i=2$ and $j=3$, yielding the array $[0,1,1,1,1]$.

Choose $i=2$ and $j=5$, yielding the array $[0,0,1,1,2]$.

Choose $i=3$ and $j=5$, yielding the array $[0,0,0,1,3]$.

Choose $i=4$ and $j=5$, yielding the array $[0,0,0,0,4]$.

In the last case, the array already satisfies the condition.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Implementation

Constructive algorithms


Solutions:
for s in [*open(0)][2::2]:
	print(sum(map(int, (a := s.lstrip('0 ').split()[:-1]))) + a.count('0'))


for s in [*open(0)][2::2]:
	a = (*map(int, s.lstrip('0 ').split()),)
	print(len(a) and a.count(0) + sum(a) - (a[-1] or 1))


for sgr in [*open(0)][2::2]:
	print(sum(map(int, (x := sgr.lstrip('0 ').split()[:-1]))) + x.count('0'))


test = int(input())
answer = list()
for i in range(test):
	room = input()
	roomsdust = list(map(int, input().split()))
	dustsum = sum(roomsdust[:-1])
	for j in range(len(roomsdust)):
		if roomsdust[j] != 0:
			break
	zerocount = roomsdust[j + 1:-1].count(0)
	answer.append(zerocount + dustsum)
for i in answer:
	print(i)


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	now = n
	for i in range(n):
		if a[i]:
			now = i
			break
	cnt = 0
	for i in range(now, n - 1):
		if a[i] == 0:
			cnt += 1
	print(sum(a[:-1]) + cnt)
for __ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	fir = next((i for (i, j) in enumerate(a) if j != 0), n)
	res = sum(a[fir:-1])
	res += a[fir:-1].count(0)
	print(res)


def solve_one_impl(nums):
	to_cut = 0
	while len(nums) - to_cut > 1 and nums[to_cut] == 0:
		to_cut += 1
	nums = nums[to_cut:]
	if len(nums) == 1:
		return 0
	zeros_cnt = 0
	nums_sum = 0
	for num in nums[:-1]:
		nums_sum += num
		zeros_cnt += 1 if num == 0 else 0
	return nums_sum + zeros_cnt

def solve_one():
	input()
	nums_inp = list(map(int, input().split()))
	return solve_one_impl(nums_inp)
t = int(input())
anss = []
for _ in range(t):
	anss.append(solve_one())
for ans in anss:
	print(ans)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	while a[i] == 0 and i < n - 1:
		i += 1
	a = a[i:n - 1]
	print(sum(a) + a.count(0))
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	j = 0
	while j < n and l[j] < 1:
		j += 1
	l = l[j:-1]
	print(sum(l) + l.count(0))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	boo = 0
	while boo < n and a[boo] < 1:
		boo += 1
	a = a[boo:-1]
	print(sum(a) + a.count(0))


def compute(arr):
	helper = len(arr) - 1
	for i in range(len(arr) - 1):
		if arr[i] != 0:
			helper = i
			break
	k = 0
	ans = 0
	for i in range(helper, len(arr) - 1):
		if arr[i] == 0:
			k += 1
		ans += arr[i]
	return ans + k
t = int(input())
arr = []
for i in range(t):
	b = input()
	a = list(map(int, input().split()))
	arr.append(a)
for i in range(len(arr)):
	print(compute(arr[i]))


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	d = 0
	for i in range(a):
		if b[i] != 0:
			d = b[i:-1].count(0)
			break
	c = sum(b[:-1])
	if c > 0:
		print(c + d)
	else:
		print(0)


def cleaner(n):
	for j in range(n):
		room_cnt = int(input())
		ash_arr = [int(x) for x in input().split()]
		len_arr = len(ash_arr)
		ans = 0
		index_ = 0
		for i in range(len_arr - 1):
			if ash_arr[i] != 0:
				index_ = i
				break
		else:
			print(ans)
			continue
		ans = ash_arr[index_:len_arr - 1].count(0) + sum(ash_arr[index_:len_arr - 1])
		print(ans)
n = int(input())
cleaner(n)


a = int(input())

def trim(L):
	for i in range(len(L)):
		if L[i] != 0:
			break
	return L[i:]

def fn(L):
	L = trim(L)
	s = 0
	for j in L[:len(L) - 1]:
		if j == 0:
			s += 1
		else:
			s += j
	return s
k = []
for i in range(a):
	b1 = int(input())
	b2 = input().split()
	b2 = [int(p) for p in b2]
	k.append(fn(b2))
for j in range(a):
	print(k[j])


a = int(input())
for i in range(a):
	n = int(input())
	l = [int(x) for x in input().split()]
	if l.count(0) != len(l):
		for i in l:
			if i != 0:
				ind = l.index(i)
				break
		l = l[ind:]
		l = l[:-1]
		ans = sum(l) + l.count(0)
		print(ans)
	else:
		print('0')


for _ in range(int(input())):
	n = int(input())
	print(sum(map(int, (a := input().lstrip('0 ').split()[:-1]))) + a.count('0'))


def resi():
	n = int(input())
	a = list(map(int, input().split()))
	brNula = 0
	for i in range(n - 1):
		if a[i] == 0:
			brNula += 1
	brNulaNaPoc = 0
	for i in range(n - 1):
		if a[i] != 0:
			break
		brNulaNaPoc += 1
	print(brNula - brNulaNaPoc + sum(a) - a[n - 1])
	return
for _ in range(int(input())):
	resi()


def main():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		i = 0
		while i < n and a[i] == 0:
			i += 1
		x = 0
		for k in range(i, n - 1):
			if a[k] == 0:
				x += 1
		print(sum(a[i:n - 1]) + x)
main()


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst1 = lst[:n - 1]
	ind = -1
	for j in range(n - 1):
		if lst1[j] != 0:
			ind = j
			break
	if ind == -1:
		print(0)
	else:
		zer = lst1[ind:].count(0)
		s = sum(lst1)
		print(zer + s)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ind1 = -1
	for i in range(n - 1):
		if nums[i] != 0:
			ind1 = i
			break
	if ind1 == -1:
		print(0)
	else:
		print(sum(nums[:n - 1]) + nums[ind1:n - 1].count(0))


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	for i in range(n):
		if A[i] > 0:
			break
	c = A[i:-1].count(0)
	print(sum(A[:-1]) + c)
t = int(input())
while t != 0:
	solve()
	t -= 1


from sys import stdin
from math import log, floor, ceil, gcd
inp = lambda : int(stdin.readline())

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		a = ra(int)
		c = 0
		s = 0
		flag = False
		for i in range(n - 1):
			if a[i] != 0:
				flag = True
				s += a[i]
			elif a[i] == 0 and flag:
				c += 1
		print(c + s)
main()


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	l = 0
	while l < n and a[l] == 0:
		l += 1
	out.append(sum(a[0:n - 1]) + a[l:n - 1].count(0))
for i in out:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for (i, x) in enumerate(arr):
		if x > 0:
			res = arr[i:n - 1].count(0) + sum(arr[i:n - 1])
			break
	print(res)


def solve():
	n = int(input())
	room = [int(i) for i in input().split()]
	res = 0
	i = 0
	while not room[i] and i < n - 1:
		i += 1
	res += room[i:-1].count(0)
	res += sum(room[i:-1])
	print(res)
	return

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


a = int(input())
for i in range(a):
	c = int(input())
	s = input().split()
	tot = 0
	tot0 = 0
	for j in s[:-1]:
		if j != '0':
			tot += int(j)
		elif tot != 0:
			tot0 += 1
	print(tot + tot0)


t = int(input())
for q in range(t):
	n = int(input())
	lst = [int(x) for x in input().split()][::-1]
	i = n - 1
	while i != 0:
		if lst[i] == 0:
			lst.pop()
			i -= 1
		else:
			break
	if lst[0] == 0:
		print(sum(lst) + lst.count(0) - 1)
	else:
		print(sum(lst) + lst.count(0) - lst[0])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sw = 0
	for (i, x) in enumerate(a[:-1]):
		if x > 0:
			sw = 1
			break
	ans = sum(a[i:-1])
	if sw:
		ans += a[i:-1].count(0)
	print(ans)


from math import *
from bisect import *
from heapq import *
from collections import *
from functools import *
x = int(input())

def f(li):
	i = 0
	for (i, j) in enumerate(li):
		if j != 0:
			break
	s = li[i:-1]
	a = s.count(0)
	b = sum(s)
	return a + b
for i in range(x):
	n = int(input())
	li = list(map(int, input().split()))
	print(f(li))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	first = 0
	while first < n - 1 and a[first] == 0:
		first += 1
	if first >= n - 1:
		print(0)
	else:
		print(sum(a[first:-1]) + a[first:-1].count(0))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ls = []
	for x in range(n - 1):
		if arr[x] != 0:
			ls = arr[x:n - 1]
			break
	add = sum(ls)
	frq = ls.count(0)
	print(add + frq)


for _ in range(int(input())):
	input()

	def del_zero(seq):
		for i in range(len(seq)):
			if seq[i] != 0:
				return seq[i:]
		else:
			return [0]
	seq = list(map(int, input().split()))
	sm = sum(seq[:-1])
	seq = del_zero(seq)
	print(seq[:-1].count(0) + sm)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n - 1):
		c += a[i] or c != 0
	print(c)


from sys import stdin, stdout

def height():
	n = int(input())
	arr = [int(x) for x in input().split()]
	count = 0
	flag = True
	for i in range(n - 1):
		if arr[i] == 0:
			if flag == False:
				count += 1
		else:
			flag = False
			count += arr[i]
	print(count)

def main():
	t = int(input())
	while t != 0:
		height()
		t -= 1
main()


for _ in ' ' * int(input()):
	n = int(input())
	l = list(input().lstrip('0 ').split(' ')[:-1])
	if l:
		s = 0
		for i in l:
			if i != '0':
				s += int(i)
			else:
				s += 1
		print(s)
	else:
		print(0)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	sList = []
	for i in range(a):
		if b[i] > 0:
			sList = b[i:-1]
			break
	print(sList.count(0) + sum(sList))


def solve():
	n = int(input())
	dust_of_rooms = list(map(int, input().split()))
	res = 0
	latest = dust_of_rooms[0]
	for i in range(n - 1):
		if dust_of_rooms[i]:
			res += dust_of_rooms[i]
			latest = dust_of_rooms[i]
		elif latest:
			res += 1
	print(res)
n_testcase = int(input())
for _ in range(n_testcase):
	solve()


for t in range(int(input())):
	n = int(input())
	l = [*map(int, input().split())]
	summ = sum(l[:n - 1])
	i = 0
	while l[i] == 0:
		if i == n - 2:
			break
		i += 1
	if l[i] == 0:
		print(summ)
	else:
		c = l[i:n - 1].count(0)
		print(summ + c)


for _ in range(int(input())):
	n = range(int(input()))
	l = list(map(int, input().split()))
	for i in n:
		if l[i] > 0:
			break
	l = l[i:-1]
	print(l.count(0) + sum(l))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if sum(a[:n - 1]) == 0:
		print(0)
	elif a[0] != 0:
		num_zero = a[:n - 1].count(0)
		print(num_zero + sum(a[:n - 1]))
	else:
		num_zero = 0
		for i in a:
			if i == 0:
				num_zero += 1
			else:
				break
		count_zero = a[num_zero:n - 1].count(0)
		print(count_zero + sum(a[num_zero:n - 1]))


import sys

def main():
	count_examples = int(input())
	for i in range(count_examples):
		rooms = int(input())
		dust_level = input()
		result = 0
		flag = False
		for (i, v) in enumerate(dust_level.split()):
			if i + 1 == rooms:
				continue
			if v == '0':
				if flag:
					result += 1
			else:
				flag = True
				result += int(v)
		sys.stdout.write(str(result) + '\n')
main()


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


for i in range(int(input())):
	n = int(input())
	values = list(map(int, input().split()))
	k = 0
	while k < n - 1:
		if values[k] > 0:
			break
		k += 1
	print(sum(values[k:n - 1]) + values[k:n - 1].count(0))


t = int(input())
for i in range(0, t):
	n = int(input())
	l = [int(x) for x in input().split()]
	for j in range(0, n):
		if l[j] != 0:
			break
	a = l.count(0)
	if l[n - 1] == 0:
		print(sum(l) + a - j - l[n - 1] - 1)
	else:
		print(sum(l) + a - j - l[n - 1])


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


reps = int(input())
for _ in range(reps):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	while i < n and arr[i] == 0:
		i += 1
	if i == n:
		print(0)
		continue
	ans = arr[i:].count(0)
	ans += sum(arr[i:n - 1]) - (arr[-1] == 0)
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = 0
	for i in range(n - 1):
		b += l[i] or b != 0
	print(b)


t = int(input())
s = []
for i in range(t):
	n = int(input())
	a = input()
	a = a.split()
	a = [int(x) for x in a]
	rez = 0
	j = 0
	while a[j] == 0 and j < n - 1:
		j += 1
	b = a[j:-1]
	print(sum(b) + b.count(0))


def func(n, lst):
	cnt = 0
	for i in range(n - 1):
		cnt += 1 if lst[i] == 0 and cnt > 0 else lst[i]
	return cnt
for i in range(int(input())):
	print(func(int(input()), list(map(int, input().split()))))


for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	lis.pop(-1)
	ind = a - 1
	for i in range(a - 1):
		if lis[i] != 0:
			ind = i
			break
	print(sum(lis[ind:]) + lis[ind:].count(0))


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


for i in range(int(input())):
	n = map(int, input().split())
	a = list(map(int, input().split()))
	j = 0
	while j < len(a) and a[j] == 0:
		j += 1
	print(a[j:-1].count(0) + sum(a[j:-1]))


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


def soln():
	n = int(input())
	a = list(map(int, input().split()))
	start = 0
	for i in range(n):
		if a[i] == 0:
			start += 1
		else:
			break
	cnt = 0
	if start == n - 1:
		print(0)
		return
	for i in range(start, n - 1):
		if a[i] == 0:
			cnt += 1
	ans = cnt + sum(a[:-1])
	print(ans)
for _ in range(int(input())):
	soln()


import sys

def rall():
	return [x.strip() for x in 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')
NT = int(rl())
for ti in range(NT):
	n = int(rl())
	array = list(map(int, rl().split(' ')))
	leading_zeroes = 0
	i = 0
	while i < n:
		if not array[i] == 0:
			break
		leading_zeroes += 1
		i += 1
	numzeroes = sum([1 if x == 0 else 0 for x in array[leading_zeroes:-1]])
	pr(numzeroes + sum(array[:-1]))


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


tc = int(input())
for t in range(tc):
	n = int(input())
	lst = list(map(int, input().split()))
	cost = 0
	bol = False
	for i in range(n - 1):
		if bol == False:
			if lst[i] != 0:
				bol = True
				cost = lst[i] + cost
		elif lst[i] != 0:
			cost = lst[i] + cost
		else:
			cost = 1 + cost
	print(cost)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for (k, j) in enumerate(l):
		if j > 0:
			l = l[k:]
			break
	l = l[:-1]
	o = l.count(0)
	x = 0
	m = 0
	if len(set(l)) == 1:
		if l[0] == 0:
			print(0)
			continue
	print(sum(l) + o)


n = int(input())
for i in range(n):
	k = int(input())
	arr = [int(i) for i in input().split()]
	index = 0
	for j in range(1, k + 1):
		if arr[j - 1] > 0:
			index = j
			break
	s = sum(arr[index - 1:k - 1]) + arr[index - 1:k - 1].count(0)
	print(s)


t = int(input())
while t:
	t -= 1
	a = int(input())
	lis = list(map(int, input().split()))
	ans = 0
	j = 0
	while j < a - 1 and lis[j] == 0:
		j += 1
	if j < a - 1:
		ans = ans + lis[j:a - 1].count(0)
		ans = ans + sum(lis[0:a - 1])
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = l[:n - 1]
	val = 0
	count = 0
	for i in l:
		if i == 0 and val == 0:
			continue
		else:
			val = 1
			if i == 0:
				count += 1
			else:
				count += i
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	z = a.count(0)
	total = sum(a) - a[n - 1]
	nonz = 0
	for i in range(n):
		if a[i] != 0:
			nonz = i
			break
	las = 0
	if a[n - 1] == 0:
		las = 1
	if total == 0:
		print(0)
	else:
		print(total + z - nonz - las)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = l.count(0)
	for i in range(len(l)):
		if l[i] == 0:
			b -= 1
		if l[i] != 0:
			break
	s = sum(l) - l[-1]
	if s == 0:
		print(0)
		continue
	q = 0
	if l[-1] == 0:
		b -= 1
	print(s + b)


t = int(input())
for i in range(t):
	tc = int(input())
	inp = list(map(int, input().split()))
	list1 = []
	z = 0
	x = inp[:-1]
	for i in range(tc):
		if inp[i] != 0:
			z = inp[i:-1].count(0)
			break
	print(z + sum(x))


for t in range(int(input())):
	flag = 0
	count = 0
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.pop()
	for i in arr:
		if i != 0:
			flag = 1
		elif flag == 1:
			count += 1
	count += sum(arr)
	print(count)


def sol(arr, n):
	i = 0
	while i < n and arr[i] == 0:
		i += 1
	if i == n:
		return 0
	count0 = 0
	for j in range(i, n - 1):
		if arr[j] == 0:
			count0 += 1
	return sum(arr[i:n - 1]) + count0
x = int(input())
for _ in range(x):
	n = int(input())
	arr = list(map(int, input().split()))
	start = 0
	print(sol(arr, n))


T = int(input())
for tt in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	sm = 0
	for x in range(len(l) - 1):
		if l[x] > 0:
			sm += l[x]
		elif l[x] == 0 and sm != 0:
			sm += 1
	print(sm)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	T_ind = -1
	for i in range(n - 1):
		if arr[i] != 0:
			T_ind = i
			break
	ans = 0
	if T_ind != -1:
		for i in range(T_ind, n - 1):
			if arr[i] == 0:
				ans += 1
			else:
				ans += arr[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	countz = 0
	ok = 0
	suma = 0
	for i in range(n - 1):
		suma += a[i]
		if not ok and a[i] != 0:
			ok = 1
		if ok and a[i] == 0:
			countz += 1
	print(suma + countz)


t = int(input())
for i in range(t):
	n = int(input())
	a1 = []
	a = list(map(int, input().split()))
	for i in range(n):
		if a[i] != 0 and i != n - 1:
			a1 = a[i:-1]
			break
	m = a1.count(0)
	h = sum(a) - a[-1]
	if h == 0:
		print(0)
	else:
		print(h + m)


t = int(input())
answer = [0] * t
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	start = 0
	while start < n and a[start] == 0:
		start += 1
	for j in range(start, n - 1):
		answer[i] += a[j]
		if a[j] == 0:
			answer[i] += 1
print(*answer, sep='\n')


class MarkTheDustSweeper:

	def findMinOperations(self, n, a):
		sum = 0
		zeros = 0
		for i in range(n - 1):
			sum += a[i]
			if a[i] == 0 and sum > 0:
				zeros += 1
		sum += zeros
		print(sum)
		return
T = int(input())
while T:
	T -= 1
	n = int(input())
	a = list(map(int, input().split()))
	MarkTheDustSweeper().findMinOperations(n, a)


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ans = 0
	d = 0
	for i in range(n - 1):
		if ls[i] > 0:
			ans += ls[i]
			if d == 0:
				d += 1
		elif d:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	pos = False
	count = 0
	for i in range(n - 1):
		if l[i] != 0:
			pos = True
			count += l[i]
		elif pos:
			count += 1
	print(count)


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


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	for i in range(n):
		if arr[i] > 0:
			r = i
			break
	y = arr[r:n - 1].count(0)
	if arr[:n - 1].count(0) == n - 1:
		print(0)
	else:
		print(str(y + sum(arr[:n - 1])))


n = int(input())
for _ in range(n):
	l = int(input())
	arr = [*map(int, input().split())]
	i = 0
	ans = 0
	while i < l and arr[i] == 0:
		i += 1
	for k in range(i, l - 1):
		if arr[k]:
			ans += arr[k]
		else:
			ans += 1
	print(ans)