Daniel is watching a football team playing a game during their training session. They want to improve their passing skills during that session.

The game involves $n$ players, making multiple passes towards each other. Unfortunately, since the balls were moving too fast, after the session Daniel is unable to know how many balls were involved during the game. The only thing he knows is the number of passes delivered by each player during all the session.

Find the minimum possible amount of balls that were involved in the game.


-----Input-----

There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^5$) — the number of players.

The second line of the test case contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$), where $a_i$ is the number of passes delivered by the $i$-th player.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

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


-----Examples-----

Input
4
4
2 3 3 2
3
1 5 2
2
0 0
4
1000000000 1000000000 1000000000 1000000000
Output
1
2
0
1


-----Note-----

In the first test case, with the only ball, the game can go like this:

$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$.

In the second test case, there is no possible way to play the game with only one ball. One possible way to play with two balls:

$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$.

$2 \rightarrow 3 \rightarrow 2 \rightarrow 1$

In the third example, there were no passes, so $0$ balls are possible.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if arr.count(0) == n:
		out += '0\n'
	else:
		out += str(max(1, max(arr) * 2 - sum(arr))) + '\n'
print(out)


import sys
from math import ceil
input = sys.stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		print(solution(a))

def solution(a):
	mx = max(a)
	total = sum(a)
	if mx == 0:
		return 0
	extra_balls = 2 * mx - total if mx > total // 2 else 1
	return extra_balls

def test():
	print(solution([0, 0, 0]) == 0)
	print(solution([2, 3, 3, 3]) == 1)
	print(solution([1, 5, 3]) == 1)
	print(solution([1, 4, 1, 1]) == 1)
	print(solution([1, 4, 1, 0]) == 2)
	print(solution([1, 5, 1, 0]) == 3)
	print(solution([1, 6, 1, 0]) == 4)
	print(solution([1000000000, 1000000000, 1000000000, 1000000000]) == 1)
main()


from sys import stdin
input = stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		pass_ = list(map(int, input().split()))
		pass_.sort()
		x = sum(pass_[:n - 1])
		y = pass_[n - 1]
		if x + y == 0:
			print(0)
		elif x >= y:
			print(1)
		else:
			print(y - x)
main()


def solve(n, arr):
	arr.sort()
	if sum(arr) == 0:
		return 0
	s = sum(arr[:-1]) + 1
	if arr[-1] <= s:
		return 1
	return arr[-1] - s + 1
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(n, arr))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	largest = max(arr)
	if largest == 0:
		print(0)
		continue
	print(max(1, 2 * largest - sum(arr)))


import sys
input = sys.stdin.readline

def solve(n, arr):
	ma = max(arr)
	S = sum(arr)
	if 2 * ma <= S:
		print(1) if S > 0 else print(0)
	else:
		print(2 * ma - S)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


lst = []
for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print(any(a) + max(0, 2 * max(a) - sum(a) - 1))


import math
from collections import Counter, defaultdict, deque
from re import I
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	m = max(a)
	s = sum(a)
	if s != 0:
		print(max(1, 2 * m - s))
	else:
		print(0)


from sys import stdin

def solve(n, arr):
	sm = sum(arr)
	if sum(arr) == 0:
		return 0
	ct = max(arr)
	return max(1, ct * 2 - sm)
input = stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(n, arr))


def main():
	import sys
	input = sys.stdin.readline

	def answer():
		n = int(input())
		a = list(map(int, input().split()))
		if set(a) == {0}:
			print(0)
			return
		print(max(2 * max(a) - sum(a), 1))
	for _ in range(int(input())):
		answer()
main()


from math import *
import sys
import heapq
cin = lambda : sys.stdin.readline().strip()
cout = sys.stdout.write

def print_test_cases(tt, ans):
	cout(f'Case #{tt}: {ans}\n')

def read_line():
	return list(map(int, cin().split()))

def solve(tt):
	cin()
	arr = read_line()
	arr = [i for i in arr if i > 0]
	if not arr:
		cout('0\n')
		return
	largest = max(arr)
	rest = sum(arr) - largest
	if largest <= rest:
		cout('1\n')
	else:
		cout(str(largest - rest) + '\n')

def main():
	T = int(cin())
	for tt in range(1, T + 1):
		solve(tt)
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a_s = sorted(a)
	s_1 = sum(a_s[:-1])
	s = s_1 + a_s[n - 1]
	if s == 0:
		print(0)
	elif a_s[n - 1] > s_1:
		print(a_s[n - 1] - s_1)
	else:
		print(1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if sum(a) >= 2 * max(a):
		if max(a) == 0:
			print(0)
		else:
			print(1)
	else:
		print(2 * max(a) - sum(a))


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	mx = max(a)
	if s == 0:
		print(0)
	elif mx - (s - mx) <= 1:
		print(1)
	else:
		print(mx - (s - mx))


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	num = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	sm = sum(arr)
	mx = max(arr)
	if sm == 0:
		ans = 0
	else:
		ans = 1
	if mx <= sm // 2:
		print(ans)
	else:
		extra = mx - (sm - mx)
		print(extra)


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if arr.count(0) == n:
		out += '0\n'
	else:
		out += str(max(1, max(arr) * 2 - sum(arr))) + '\n'
print(out)


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

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

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	mx = max(arr)
	sm = sum(arr)
	if sm == 0:
		print(0)
		continue
	rem = sm - mx
	if rem >= mx - 1:
		print(1)
	else:
		print(mx - rem)


def main():
	s = []
	t = int(input())
	for test in range(t):
		n = int(input())
		p_per_player = list(input().split())
		somma = 0
		for i in range(n):
			p_per_player[i] = int(p_per_player[i])
		massimo = max(p_per_player)
		p_per_player.remove(massimo)
		for e in p_per_player:
			somma += e
		if massimo == 0:
			s.append(0)
		elif massimo > somma:
			s.append(massimo - somma)
		else:
			s.append(1)
	for ss in s:
		print(int(ss))
main()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	mi = min(a)
	tot = sum(a)
	if mi == mx == 0:
		print(0)
		continue
	if 2 * mx <= tot:
		print(1)
	else:
		print(2 * mx - tot)


import sys
count = int(sys.stdin.readline())
ans = [0] * count
for i in range(count):
	n = int(sys.stdin.readline())
	players = list(map(int, sys.stdin.readline().split(' ')))
	max = 0
	sum = 0
	for j in range(n):
		sum += players[j]
		if players[j] > max:
			sum += max
			max = players[j]
			sum -= players[j]
	if sum == 0 and max == 0:
		ans[i] = 0
	elif max - sum <= 1:
		ans[i] = 1
	else:
		ans[i] = max - sum
for j in range(count):
	print(ans[j])


t = int(input())
out = []
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.count(0) == n:
		out.append('0\n')
	else:
		out.append(str(max(1, max(arr) * 2 - sum(arr))) + '\n')
print(''.join(out))


t = int(input())
result = []
for i1 in range(t):
	n = int(input())
	passes = [int(i2) for i2 in input().split()]
	passes.sort()
	max_passes = passes[-1]
	sum_rest = sum(passes)
	balls = 2 * max_passes - sum_rest
	if balls < 1:
		if sum_rest == 0:
			result.append(0)
		else:
			result.append(1)
	else:
		result.append(balls)
for i3 in result:
	print(i3)


import sys
n = int(sys.stdin.readline().strip())
for i in range(n):
	a = int(sys.stdin.readline().strip())
	s = list(map(int, sys.stdin.readline().strip().split()))
	if s.count(0) == len(s):
		print(0)
	else:
		d = sorted(s)
		print(max(d[-1] - sum(d[:-1]), 1))


from collections import defaultdict, deque
import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if a[0] == 0 and a[-1] == 0:
		print(0)
	else:
		print(1 if 2 * max(a) <= sum(a) else 2 * max(a) - sum(a))


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in [0] * t:
	n = int(input())
	a = list(map(int, input().split()))
	b = sum(a) - max(a) + 1
	if max(a) == 0:
		print(0)
	elif max(a) > b:
		print(max(a) - b + 1)
	else:
		print(1)


import sys

def _input_iter():
	for line in sys.stdin:
		for part in line.strip().split(' '):
			stripped = part.strip()
			if stripped:
				yield stripped
stream = _input_iter()

def read_int():
	return int(next(stream))

def read_str():
	return next(stream)

def run():
	n = read_int()
	a = []
	for i in range(n):
		a.append(read_int())
	a = sorted(a, reverse=True)
	if a[0] == 0:
		print(0)
		return
	print(max(1, 2 * max(a) - sum(a)))
test_cases = read_int()
for _ in range(test_cases):
	run()


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	m = max(a)
	s = sum(a)
	if m == 0:
		out.append(0)
	elif m > s - m:
		out.append(2 * m - s)
	else:
		out.append(1)
for i in out:
	print(i)


t = int(input())
out = []
a = ''
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	sum_ = sum(l)
	max_ = max(l)
	if sum_ == 0:
		out.append('0')
		a += '0'
	else:
		out.append(str(max(1, 2 * max_ - sum_)))
		a += out[-1]
for x in out:
	print(x)


from array import *
t = int(input())
ans = []
while t > 0:
	t -= 1
	i = 0
	n = int(input())
	a = array('i', list(map(int, input().split())))
	total = sum(a)
	mx = max(a)
	if total == 0:
		ans.append(0)
		continue
	total = total - mx
	if total >= mx - 1:
		ans.append(1)
	else:
		ans.append(1 + (mx - total - 1))
for i in ans:
	print(i)


for iters in range(int(input())):
	n = input()
	vals = [int(i) for i in input().split(' ')]
	sumn = sum(vals)
	maxn = max(vals)
	s = 2 * maxn - sumn
	if maxn == 0:
		print(0)
	elif s <= 1:
		print(1)
	else:
		print(s)


import collections
import math

def solve(a, n):
	ts = sum(a)
	if ts == 0:
		print(0)
	else:
		mx = max(a)
		if ts - mx < mx:
			print(mx - (ts - mx))
		else:
			print(1)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	solve(a, n)


try:
	for _ in range(0, int(input())):
		n = int(input())
		mylist = list(map(int, input().split()))
		mylist.sort()
		sumexceptlast = sum(mylist[:n - 1])
		if sumexceptlast + mylist[n - 1] == 0:
			print(0)
			continue
		elif sumexceptlast >= mylist[n - 1]:
			print(1)
			continue
		else:
			print(mylist[n - 1] - sumexceptlast)
			continue
except:
	pass


for _ in range(int(input())):
	n = int(input())
	a = sorted([int(i) for i in input().split()])
	diff = a[-1] - sum(a[:-1])
	if not a[-1]:
		print(0)
	elif diff <= 1:
		print(1)
	else:
		print(diff)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = a[-1] - (sum(a) - a[-1])
	if sum(a) == 0:
		print(0)
	else:
		print(1) if s <= 0 else print(s)


import collections
import math

def main():
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = 0
	totalsum = sum(a)
	if totalsum == 0:
		print(0)
	else:
		mx = max(a)
		if totalsum - mx < mx:
			print(mx - (totalsum - mx))
		else:
			print(1)
t = int(input())
while t > 0:
	main()
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	mx = max(a)
	s -= mx
	if sum(a) == 0:
		print(0)
	elif mx > s:
		print(mx - s)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) == 0:
		print(0)
	else:
		m = max(a)
		s = sum(a)
		print(max(2 * m - s, 1))


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	maxNum = max(nums)
	rest = sum(nums) - maxNum
	if rest >= maxNum:
		if maxNum == 0:
			print(0)
		else:
			print(1)
	else:
		print(maxNum - rest)


for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	maxx = max(list1)
	summ = sum(list1)
	if maxx == 0:
		print(0)
	else:
		print(max(1, 2 * maxx - summ))


T_cases = int(input())
for i in range(T_cases):
	n = int(input())
	Shoots = list(map(int, input().split()))
	maxi = max(Shoots)
	Shoots.remove(maxi)
	Sum = 0
	for q in Shoots:
		Sum += q
	if maxi - Sum < 2 and maxi != 0:
		print(1)
	elif maxi - Sum >= 2:
		print(maxi - Sum)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	m = max(arr)
	s = sum(arr)
	if s == 0:
		print(0)
	elif 2 * m > s:
		print(2 * m - s)
	else:
		print(1)


for _ in range(int(input())):
	input()
	a = [int(i) for i in input().split()]
	if max(a) * 2 <= sum(a) and a != [0] * len(a):
		print(1)
	else:
		print(max(a) * 2 - sum(a))


T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if s == 0:
		print(0)
	else:
		m = max(a)
		rest = s - m
		k = m - rest
		if k <= 0:
			print(1)
		else:
			print(k)


x = int(input())
for ll in range(x):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	z = sum(a) - a[n - 1]
	if sum(a) == 0:
		print(0)
	elif z + 1 >= a[n - 1]:
		print(1)
	else:
		print(a[n - 1] - z)


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


import collections
import math

def main():
	nu = int(input())
	an = list(map(int, input().split()))
	ts = sum(an)
	if ts == 0:
		print(0)
	else:
		mx = max(an)
		if ts - mx < mx:
			print(mx - (ts - mx))
		else:
			print(1)
t = int(input())
while t > 0:
	main()
	t -= 1


def solveB(n, a):
	a = sorted(a)
	maximum = max(a)
	total = sum(a) - maximum
	if maximum > total:
		return maximum - total
	elif maximum == 0:
		return 0
	else:
		return 1
num_tests = int(input().split()[0])
for t in range(num_tests):
	n = int(input())
	a = [int(value) for value in input().split()]
	print(solveB(n, a))


for i in range(int(input())):
	n = int(input())
	pas = list(map(int, input().split()))
	mx = max(pas)
	s = sum(pas) - mx
	if mx == 0:
		print(0)
	else:
		print(max(1, mx - s))


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	nums.sort()
	if nums[-1] == 0:
		print(0)
	elif nums[-1] > sum(nums[:-1]):
		print(nums[-1] - sum(nums[:-1]))
	else:
		print(1)


n = input()
for elem in range(int(n)):
	number_of_players = int(input())
	players_string = input()
	players = [int(p) for p in players_string.split()]
	max_pass = max(players)
	players.remove(max_pass)
	interval = max_pass - sum(players)
	if interval > 1:
		print(interval)
	elif max_pass != 0:
		print(1)
	else:
		print(0)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) == 0:
		print(0)
		return
	else:
		print(max(2 * max(a) - sum(a), 1))
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = sum(a)
	if p == 0:
		print(0)
	elif 2 * max(a) <= p:
		print(1)
	else:
		print(2 * max(a) - p)


for i in range(int(input())):
	(Size, passes) = (input(), list(map(int, input().split())))
	passes.sort()
	temp = -passes[-1]
	for i in passes:
		temp += i
	if passes[-1] == 0:
		print(0)
		continue
	if passes[-1] > temp:
		print(passes[-1] - temp)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	total = sum(a)
	maximum = max(a)
	if total == 0:
		print(0)
		continue
	if 2 * maximum <= total:
		print(1)
	else:
		print(2 * maximum - total)


for t in range(int(input())):
	n = int(input())
	passes = list(map(int, input().split()))
	passes.sort()
	if passes.count(0) == len(passes):
		print(0)
	elif passes[-1] - sum(passes[:-1]) <= 1:
		print(1)
	else:
		print(passes[-1] - sum(passes[:-1]))


for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	if sum(a) == 0:
		print(0)
	else:
		s = max(a) - (sum(a) - max(a))
		if s <= 0:
			print(1)
		else:
			print(s)


def task(a):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	(total, high) = (0, 0)
	while i < n:
		total += arr[i]
		if arr[i] > high:
			high = arr[i]
		i += 1
	if total == 0:
		print(0)
		return
	elif 2 * high <= total:
		print(1)
		return
	else:
		print(2 * high - total)
		return
t = int(input())
for a in range(1, t + 1):
	task(a)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	temp = 2 * max(a) - sum(a)
	if a.count(0) == n:
		print(0)
	elif temp <= 0:
		print(1)
	else:
		print(temp)


def solv(L):
	if not sum(L):
		return 0
	t = max(L) * 2 - sum(L)
	return 1 if t <= 0 else t
for _ in range(int(input())):
	input()
	L = list(map(int, input().split()))
	print(solv(L))


def solve(testcase):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	max_ele = max(arr)
	if max_ele == 0:
		print(0)
		return
	first = 0
	while first != n - 2 and arr[-1] > arr[-2]:
		arr[-1] -= arr[first]
		first += 1
	ans = 1
	print(max(1, arr[-1] - arr[-2]))
n = int(input())
for _ in range(n):
	solve(n)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	max1 = max(a)
	sum1 = sum(a)
	if sum1 == 0:
		print(0)
	elif max1 <= sum1 - max1:
		print(1)
	else:
		print(max1 - (sum1 - max1))


for _ in range(int(input())):
	n = input()
	a = [int(i) for i in input().split()]
	m = max(a)
	s = sum(a) - m
	if s == 0:
		print(m)
		continue
	print(max(1, m - s))


n = int(input())
for i in range(n):
	input()
	l = tuple(map(int, input().split()))
	s = sum(l)
	m = max(l)
	if s == 0:
		print(0)
	elif 2 * m - s > 0:
		print(2 * m - s)
	else:
		print(1)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	check = sum(a) - a[-1]
	if sum(a) == 0:
		print(0)
	elif check - a[-1] >= -1:
		print(1)
	else:
		print(a[-1] - check)
for i in range(int(input())):
	solve()


for i in range(int(input())):
	input()
	x = list(map(int, input().split(' ')))
	x.sort(reverse=True)
	k = x[0]
	if sum(x) == 0:
		print(0)
	elif sum(x) >= 2 * k:
		print(1)
	else:
		print(2 * k - sum(x))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	c = 0
	for k in lst:
		if k > 0:
			c += 1
			break
	if c == 0:
		print(0)
	else:
		su = sum(lst)
		ele = max(lst)
		if 2 * ele <= su:
			print(1)
		else:
			print(2 * ele - su)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	mi = min(a)
	tot = sum(a)
	if mi == mx == 0:
		print(0)
		continue
	if 2 * mx <= tot:
		print(1)
	else:
		print(2 * mx - tot)


for _ in range(int(input())):
	n = int(input())
	v = [int(x) for x in input().split()]
	mx = max(v)
	if mx == 0:
		print(0)
		continue
	s = sum(v)
	s -= mx
	if mx > s + 1:
		print(mx - s)
	else:
		print(1)


def sqsum(p):
	if max(p) == 0:
		return 0
	else:
		m = max(p)
		s = sum(p)
		if m <= s - m:
			return 1
		else:
			return 2 * m - s
t = int(input())
for j in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	print(sqsum(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	d = a[0] - sum(a[1:])
	if sum(a) == 0:
		res = 0
	elif d < 2:
		res = 1
	else:
		res = d
	print(res)


for i in range(int(input())):
	input()
	s = list(map(int, input().split()))
	m = max(s)
	su = sum(s) - m
	if sum(s) == 0:
		print(0)
	elif m - su <= 1:
		print(1)
	else:
		print(m - su)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	m = l[0]
	for i in l:
		s += i
		m = max(m, i)
	s -= m
	if s == 0 and m == 0:
		print(0)
	elif s >= m:
		print(1)
	else:
		print(m - s)


t = int(input())
while t > 0:
	n = int(input())
	x = list(map(int, input().split()))
	ans = 0 if sum(x) == 0 else max(2 * max(x) - sum(x), 1)
	print(ans)
	t -= 1