There are $n$ trees in a park, numbered from $1$ to $n$. The initial height of the $i$-th tree is $h_i$.

You want to water these trees, so they all grow to the same height.

The watering process goes as follows. You start watering trees at day $1$. During the $j$-th day you can:

Choose a tree and water it. If the day is odd (e.g. $1, 3, 5, 7, \dots$), then the height of the tree increases by $1$. If the day is even (e.g. $2, 4, 6, 8, \dots$), then the height of the tree increases by $2$.

Or skip a day without watering any tree.

Note that you can't water more than one tree in a day.

Your task is to determine the minimum number of days required to water the trees so they grow to the same height.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases.

The first line of the test case contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of trees.

The second line of the test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$), where $h_i$ is the height of the $i$-th tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ ($\sum n \le 3 \cdot 10^5$).


-----Output-----

For each test case, print one integer — the minimum number of days required to water the trees, so they grow to the same height.


-----Examples-----

Input
3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4
Output
4
3
16


-----Note-----

Consider the first test case of the example. The initial state of the trees is $[1, 2, 4]$.

During the first day, let's water the first tree, so the sequence of heights becomes $[2, 2, 4]$;

during the second day, let's water the second tree, so the sequence of heights becomes $[2, 4, 4]$;

let's skip the third day;

during the fourth day, let's water the first tree, so the sequence of heights becomes $[4, 4, 4]$.

Thus, the answer is $4$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics

Greedy algorithms


Solutions:
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	m = int(input())
	l = list(map(int, input().split()))
	p = max(l)
	s = 0
	s2 = 0
	o = 0
	for i in range(m):
		s = s + p - l[i]
		s2 = s2 + p + 1 - l[i]
		if (p - l[i]) % 2 == 1:
			o = o + 1
	ans = 2 * (s // 3) + s % 3
	if o > s // 3 + 1:
		ans = o * 2 - 1
	ans2 = 2 * (s2 // 3) + s2 % 3
	if m - o > s2 // 3 + 1:
		ans2 = (m - o) * 2 - 1
	print(min(ans, ans2))


def getmin(arr1, c):
	arr = list(arr1)
	mx = max(arr)
	for i in range(n):
		arr[i] = mx + c - arr[i]
	s = sum(arr)
	c = 0
	for i in arr:
		if i % 2 == 1:
			c += 1
	d = 2 * c - 1
	s -= c * 1 + (c - 1) * 2
	if s <= 0:
		pass
	else:
		t = s // 3
		rem = s % 3
		if rem != 0:
			d += 1
		d += 2 * t
	return d

def solve(arr1):
	return min(getmin(arr1, 0), getmin(arr1, 1))
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr1 = [int(x) for x in input().split()]
	print(solve(arr1))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	a = l.count(l[-1])
	(odd, even) = (0, 0)
	for i in l:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	su = sum(l[:n - a])
	needed = l[-1] * (n - a) - su
	if l[-1] % 2 == 0:
		(p1, p2) = (odd, even)
	else:
		(p1, p2) = (even, odd)
	ans = max(2 * (needed // 3) + needed % 3, 2 * p1 - 1)
	needed += n
	ans2 = max(2 * (needed // 3) + needed % 3, 2 * p2 - 1)
	print(min(ans, ans2))


def calc(arr: list, maximum: int):
	(odd, even) = (0, 0)
	days = 0
	for element in arr:
		remaining = maximum - element
		odd += remaining % 2
		even += remaining // 2
	mutual_days = min(odd, even)
	days += 2 * mutual_days
	even -= mutual_days
	odd -= mutual_days
	if odd != 0:
		days += 2 * odd - 1
	days += 4 * (even // 3)
	remainder = even % 3
	if remainder == 1:
		days += 2
	elif remainder == 2:
		days += 3
	return days
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	print(min(calc(a, max(a)), calc(a, max(a) + 1)))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	(x1, x2) = (0, 0)
	mx = max(a)
	(ans1, ans2) = (0, 0)
	for x in a:
		t = mx - x
		if t % 2 == 1:
			x1 += 1
		x2 += t // 2
	if x1 == x2:
		ans1 = x1 * 2
	elif x1 > x2:
		t = x1 - x2
		ans1 = t * 2 - 1 + x2 * 2
	else:
		t = x2 - x1
		res = 0
		if t % 3 == 0:
			res = t // 3 * 4
		else:
			res = t // 3 * 4 + t % 3 + 1
		ans1 = x1 * 2 + res
	mx += 1
	(x1, x2) = (0, 0)
	for x in a:
		t = mx - x
		if t % 2 == 1:
			x1 += 1
		x2 += t // 2
	if x1 == x2:
		ans2 = x1 * 2
	elif x1 > x2:
		t = x1 - x2
		ans2 = t * 2 - 1 + x2 * 2
	else:
		t = x2 - x1
		res = 0
		if t % 3 == 0:
			res = t // 3 * 4
		else:
			res = t // 3 * 4 + t % 3 + 1
		ans2 = x1 * 2 + res
	print(min(ans1, ans2))
for _ in range(int(input())):
	solve()


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	h = [int(x) for x in input().split()]
	target = max(h)
	odds = 0
	evens = 0
	for x in h:
		evens += (target - x) // 2
		odds += (target - x) % 2
	total = odds * 2 - 1
	evens -= odds - 1
	if evens > 0:
		total += evens // 3 * 4
		total += max(0, evens % 3 * 2 - 1)
	target = max(h) + 1
	odds = 0
	evens = 0
	for x in h:
		evens += (target - x) // 2
		odds += (target - x) % 2
	total2 = odds * 2 - 1
	evens -= odds - 1
	if evens > 0:
		total2 += evens // 3 * 4
		total2 += max(0, evens % 3 * 2 - 1)
	out += str(min(total, total2)) + '\n'
print(out)


import sys
input = sys.stdin.readline

def solve(n, h):
	h.sort()
	target = h[-1]

	def find(target):
		ans = 0
		cnt = {1: 0, 2: 0}
		for i in range(n):
			if (target - arr[i]) % 2:
				cnt[1] += 1
			cnt[2] += (target - arr[i]) // 2
		if cnt[1] == cnt[2]:
			return 2 * cnt[1]
		elif cnt[2] > cnt[1]:
			ans = 2 * cnt[1] + (cnt[2] - cnt[1]) // 3 * 4
			if (cnt[2] - cnt[1]) % 3 != 0:
				ans += (cnt[2] - cnt[1]) % 3 + 1
			return ans
		else:
			return 2 * cnt[2] + (cnt[1] - cnt[2] - 1) * 2 + 1
	res = min(find(target), find(target + 1))
	print(res)
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


def solve(m, a):
	ev = od = 0
	for i in a:
		ev += (m - i) // 2
		od += (m - i) % 2
	if od >= ev:
		return od * 2 - (od != ev)
	ev = (ev - od) * 2
	return od * 2 + ev // 3 * 2 + ev % 3
I = lambda : map(int, input().split())
(t,) = I()
for _ in [1] * t:
	(n,) = I()
	a = [*I()]
	m = max(a)
	print(min(solve(m, a), solve(m + 1, a)))


for q in range(int(input())):
	n = input()
	arr = [int(x) for x in input().split()]

	def helper(h, ans):
		(odd, even) = (0, 0)
		for item in arr:
			even += (h - item) // 2
			odd += (h - item) % 2
		t = min(odd, even)
		ans += 2 * t
		odd -= t
		even -= t
		ans += 4 * (even // 3)
		rem = even % 3
		if rem == 1:
			ans += 2
		elif rem == 2:
			ans += 3
		if odd:
			ans += 2 * odd - 1
		return ans
	m = max(arr)
	ans = min(helper(m, 0), helper(m + 1, 0))
	print(ans)


inp = lambda : list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	t = inp()
	c = 0
	m = max(t)

	def mm(m):
		n1 = n2 = 0
		tot = 0
		for i in t:
			n1 += (m - i) % 2
			n2 += (m - i) // 2
		return n1 * 2 - 1 if n2 < n1 else (n2 * 2 + n1) // 3 * 2 + (n2 * 2 + n1) % 3
	print(min(mm(m), mm(m + 1)))


def calc(a: list, k: int):
	(c1, c2) = (0, 0)
	for item in a:
		if (k - item) % 2 == 1:
			c1 += 1
		c2 += (k - item) // 2
	if c1 > c2:
		return c1 * 2 - 1
	if c1 == c2:
		return c1 * 2
	c2 = (c2 - c1) * 2
	return c1 * 2 + c2 // 3 * 2 + c2 % 3
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	print(min(calc(a, max(a)), calc(a, max(a) + 1)))


t = int(input())
test_cases = []
for i in range(t):
	lst = []
	n = int(input())
	inp = list(map(int, input().split()))
	for i in range(n):
		lst.append(inp[i])
	test_cases.append(lst)

def countDays(lst, max_h):
	max_height = max_h
	ones = 0
	twos = 0
	for i in range(len(lst)):
		diff = max_height - lst[i]
		twos += int(diff / 2)
		ones += diff % 2
	days = 0
	min_days = min(ones, twos)
	days = 2 * min_days
	twos -= min_days
	ones -= min_days
	days += 4 * int(twos / 3)
	remainder = twos % 3
	if remainder == 1:
		days += 2
	elif remainder == 2:
		days += 3
	if ones != 0:
		days += 2 * ones - 1
	return days
answers = []
for lst in test_cases:
	minimun = min(countDays(lst, max(lst)), countDays(lst, max(lst) + 1))
	answers.append(minimun)
for i in answers:
	print(i)


def solve(N, A):
	res = float('inf')
	mx = max(A)
	for m in [mx, mx + 1]:
		two = one = 0
		for a in A:
			two += (m - a) // 2
			one += (m - a) % 2
		if two - one >= 2:
			t = (two - one + 1) // 3
			one += 2 * t
			two -= t
		if two < one:
			res = min(res, one * 2 - 1)
		elif two == one:
			res = min(res, one * 2)
		elif two == one + 1:
			res = min(res, two * 2)
		else:
			return False
	return res

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		out = solve(N, A)
		print(out)
main()


def minimumDays(array):

	def solve(array, max_height):
		(ones, twos) = (0, 0)
		for height in array:
			ones += (max_height - height) % 2
			twos += (max_height - height) // 2
		if ones > twos:
			return ones * 2 - 1
		elif ones == twos:
			return ones * 2
		twos = (twos - ones) * 2
		return ones * 2 + twos // 3 * 2 + twos % 3
	max_height = max(array)
	return min(solve(array, max_height), solve(array, max_height + 1))

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		out = minimumDays(A)
		print(out)
main()


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)
	ans = float('inf')
	for i in range(2):
		mx += i
		one = 0
		two = 0
		for j in range(n):
			diff = mx - arr[j]
			two += diff // 2
			one += diff % 2
		tot = two * 2 + one
		s = tot // 3 * 2
		if tot % 3 == 1:
			s += 1
		elif tot % 3 == 2:
			s += 2
		ans = min(ans, max(one * 2 - 1, s))
	print(ans)


def solve(lst, h):
	even = 0
	odd = 0
	ans = 0
	for i in range(len(lst)):
		x = h - lst[i]
		even += int(x / 2)
		odd += x % 2
	if odd > even:
		ans = 2 * odd - 1
	elif odd == even:
		ans = 2 * odd
	else:
		y = even - odd
		if y % 3 == 0:
			ans += 2 * odd
			ans += y / 3 * 4
		elif y % 3 == 1:
			ans += 2 * odd
			ans += (y - 1) / 3 * 4 + 2
		else:
			ans += 2 * odd
			ans += (y - 2) / 3 * 4 + 3
	return int(ans)
for _ in range(int(input())):
	n = int(input())
	inp = list(map(int, input().split()))
	height = max(inp)
	print(min(solve(inp, height), solve(inp, height + 1)))


def solve(v1):
	m = max(v1)
	ans = float('inf')
	for i in range(2):
		m += i
		twoCount = 0
		oneCount = 0
		for i in v1:
			if m - i > 0:
				oneCount += (m - i) % 2
				twoCount += (m - i) // 2
		total = oneCount + twoCount * 2
		need = total // 3 * 2 + total % 3
		ans = min(ans, max(need, oneCount * 2 - 1))
	return ans

def main():
	size = int(input())
	for i in range(size):
		input()
		v1 = list(map(int, input().split(' ')))
		print(solve(v1))
main()


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	e = 0
	ee = 0
	o = 0
	oo = 0
	for i in range(n):
		if (m - l[i]) % 2 == 1:
			e += (m - l[i] - 1) // 2
			o += 1
			ee += (m - l[i] + 1) // 2
		else:
			e += (m - l[i]) // 2
			oo += 1
			ee += (m - l[i]) // 2
	ans = 0
	anss = 0
	if o > e:
		ans = 2 * o - 1
	else:
		ans = 2 * o + 2 * (2 * (e - o) // 3) + 2 * (e - o) % 3
	if oo > ee:
		anss = 2 * oo - 2
	else:
		anss = 2 * oo + 2 * (2 * (ee - oo) // 3) + 2 * (ee - oo) % 3
	print(min(ans, anss))
	t -= 1


def solve(v1):
	m = max(v1)
	ans = float('inf')
	for i in range(2):
		m += i
		even = 0
		odd = 0
		for i in v1:
			if m - i > 0:
				odd += (m - i) % 2
				even += (m - i) // 2
		total = odd + even * 2
		need = total // 3 * 2 + total % 3
		ans = min(ans, max(need, odd * 2 - 1))
	return ans
n = int(input())
for i in range(n):
	input()
	v1 = list(map(int, input().split(' ')))
	print(solve(v1))


def qq(q1, q2):
	if q2 >= q1:
		ans = 2 * q1
		rest = q2 - q1
		(triad, rest) = divmod(rest, 3)
		ans += triad << 2
		if rest:
			ans += rest + 1
	else:
		ans = 2 * q1 - 1
	return ans
t = int(input())
while t:
	t -= 1
	n = int(input())
	p_even = 0
	q_even = 0
	p_odd = 0
	q_odd = 0
	m = 0
	for h in map(int, input().split()):
		if h > m:
			d = h - m
			dd = d >> 1
			p_even += dd * q_even
			p_odd += dd * q_odd
			if d & 1:
				if m & 1:
					p_even += q_even
				else:
					p_odd += q_odd
			m = h
		if h & 1:
			q_odd += 1
			p_odd += m - h >> 1
		else:
			q_even += 1
			p_even += m - h >> 1
	n1 = q_even if m & 1 else q_odd
	n2 = p_even + p_odd
	m1 = q_odd if m & 1 else q_even
	m2 = n2 + n1
	print(min(qq(n1, n2), qq(m1, m2)))


for t in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	(a, b) = (0, 0)
	m = max(x)
	for i in x:
		if (m - i) % 2 == 1:
			a += 1
			b += (m - i - 1) // 2
		else:
			b += (m - i) // 2
	if b > a:
		(a, b) = (a + 2 * ((b - a) // 3), b - (b - a) // 3)
	if b - a == 2:
		a += 2
		b -= 1
	(a, b) = ((a - 1) * 2 + 1, b * 2)
	m = max(a, b)
	z = m
	m = max(x) + 1
	(a, b) = (0, 0)
	for i in x:
		if (m - i) % 2 == 1:
			a += 1
			b += (m - i - 1) // 2
		else:
			b += (m - i) // 2
	if b > a:
		(a, b) = (a + 2 * ((b - a) // 3), b - (b - a) // 3)
	if b - a == 2:
		a += 2
		b -= 1
	(a, b) = ((a - 1) * 2 + 1, b * 2)
	m = max(a, b)
	print(min(z, m))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = max(l)
	one = 0
	two = 0
	best = 10 ** 9
	for i in l:
		two += (a - i) // 2
		one += (a - i) % 2
	x = (two - one) // 3
	if x >= 0:
		two -= x
		one += 2 * x
		if one <= two:
			best = 2 * two
		else:
			best = 2 * one - 1
		two -= 1
		one += 2
		if one <= two:
			best = min(best, 2 * two)
		else:
			best = min(best, 2 * one - 1)
	elif one <= two:
		best = min(best, 2 * two)
	else:
		best = min(best, 2 * one - 1)
	a += 1
	one = 0
	two = 0
	for i in l:
		two += (a - i) // 2
		one += (a - i) % 2
	x = (two - one) // 3
	if x >= 0:
		two -= x
		one += 2 * x
		if one <= two:
			best = min(best, 2 * two)
		else:
			best = min(best, 2 * one - 1)
		two -= 1
		one += 2
		if one <= two:
			best = min(best, 2 * two)
		else:
			best = min(best, 2 * one - 1)
	elif one <= two:
		best = min(best, 2 * two)
	else:
		best = min(best, 2 * one - 1)
	print(best)


t = int(input())
for i in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	tallest = max(h)
	results = []
	for x in [tallest, tallest + 1]:
		result = 0
		odddays = 0
		evendays = 0
		for tree in h:
			odddays += (x - tree) % 2
			evendays += (x - tree) // 2
		if evendays > odddays:
			extra_evendays = evendays - odddays
			odddays_replacing_evendays = extra_evendays // 3
			evendays -= odddays_replacing_evendays
			odddays += 2 * odddays_replacing_evendays
			if extra_evendays % 3 == 2:
				evendays -= 1
				odddays += 2
		result = max(odddays * 2 - 1, evendays * 2)
		results.append(result)
	print(min(results))


x = int(input())

def days(e, o):
	if e >= o:
		if (e - o) % 3 == 0:
			d = 2 * o + 4 * ((e - o) // 3)
		elif (e - o) % 3 == 1:
			d = 2 * o + 4 * ((e - o) // 3) + 2
		else:
			d = 2 * o + 4 * ((e - o) // 3) + 3
	elif o > e:
		d = 2 * o - 1
	return d

def k(arr_diff):
	e = int(0)
	o = int(0)
	for j in arr_diff:
		e += j // 2
		o += j % 2
	return (e, o)
for i in range(x):
	n = int(input())
	s = input()
	arr = [int(j) for j in s.split(' ')]
	d1 = 0
	d2 = 0
	arr_ch = []
	m = 0
	for j in arr:
		if j > m:
			m = j
	arr_diff = [int(m - k) for k in arr]
	arr_diff1 = []
	zer = 0
	for p in arr_diff:
		if p != 0:
			arr_diff1.append(p + 1)
		else:
			zer += 1
			arr_diff1.append(p)
	(e, o) = k(arr_diff)
	(e1, o1) = k(arr_diff1)
	d1 = days(e, o)
	d2 = days(e1, o1 + zer)
	if d1 < d2:
		print(d1)
	else:
		print(d2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	ans = float('inf')
	for z in range(2):
		mx += z
		(twos, ones) = (0, 0)
		for i in range(n):
			diff = mx - a[i]
			twos += diff // 2
			ones += diff % 2
		res = 0
		days = min(twos, ones)
		res = 2 * days
		twos -= days
		ones -= days
		res += 4 * (twos // 3)
		rem = twos % 3
		if rem == 1:
			res += 2
		elif rem == 2:
			res += 3
		if ones:
			res += 2 * ones - 1
		ans = min(ans, res)
	print(ans)


n = int(input())
for i in range(n):
	l = int(input())
	values = list(map(int, input().split()))
	results = []
	for maximum in [max(values), max(values) + 1]:
		n_odd = 0
		n_even = 0
		diffs = [maximum - el for el in values if el != maximum]
		for d in diffs:
			n_odd += d % 2
			n_even += d // 2
		minimum = min(n_odd, n_even)
		days = minimum * 2
		n_odd -= minimum
		n_even -= minimum
		if n_odd == 0:
			by_odd = n_even // 3
			days += by_odd * 4
			n_even %= 3
			if n_even:
				days += +(2 if n_even == 1 else 3)
		else:
			days += n_odd * 2 - 1
		results.append(days)
	print(min(results))


t = int(input())
while t:
	n = int(input())
	h = []
	for i in input().split():
		h.append(int(i))
	hmax = max(h)
	odd = even = 0
	for hi in h:
		ht = hmax - hi
		odd += ht % 2 & 1
		even += ht // 2
	if odd < even:
		even -= odd
		ans1 = 2 * (odd + even // 3 * 2) + (even % 3 + 1 if even % 3 else 0)
	elif odd == even:
		ans1 = odd * 2
	else:
		odd -= even
		ans1 = even * 2 + odd * 2 - 1
	hmax += 1
	odd = even = 0
	for hi in h:
		ht = hmax - hi
		odd += ht % 2 & 1
		even += ht // 2
	if odd < even:
		even -= odd
		ans2 = 2 * (odd + even // 3 * 2) + (even % 3 + 1 if even % 3 else 0)
	elif odd == even:
		ans2 = odd * 2
	else:
		odd -= even
		ans2 = even * 2 + odd * 2 - 1
	print(min(ans1, ans2))
	t -= 1


n_testcases = int(input())
for i in range(n_testcases):
	n_trees = int(input())
	trees_height = input().split(' ')
	trees_height = [int(l) for l in trees_height]
	possible_required_days = []
	possible_max_heights = [max(trees_height), max(trees_height) + 1]
	for max_height in possible_max_heights:
		ones = 0
		twos = 0
		days_needed = 0
		for tree_height in trees_height:
			diff = max_height - tree_height
			twos += diff // 2
			ones += diff % 2
		consecutive_pattern = min(twos, ones)
		days_needed = consecutive_pattern * 2
		twos -= consecutive_pattern
		ones -= consecutive_pattern
		days_needed += twos // 3 * 4
		remainder = twos % 3
		if remainder == 1:
			days_needed += 2
		elif remainder == 2:
			days_needed += 3
		if ones:
			days_needed += 2 * ones - 1
		possible_required_days.append(days_needed)
	print(min(possible_required_days))


def count_days(h, array):
	odd = 0
	even = 0
	for i in range(len(array)):
		diff = h - array[i]
		even += diff // 2
		odd += diff % 2
	days = 0
	cnt = min(odd, even)
	days = 2 * cnt
	even -= cnt
	odd -= cnt
	days += 4 * (even // 3)
	rem = even % 3
	if rem == 1:
		days += 2
	elif rem == 2:
		days += 3
	if odd != 0:
		days += 2 * odd - 1
	return days
t = int(input())
for i in range(t):
	arr_len = input()
	s = input()
	array = s.split()
	array = [int(i) for i in array]
	answers = []
	h = max(array)
	answers.append(count_days(h, array))
	answers.append(count_days(h + 1, array))
	answers.append(count_days(h + 2, array))
	print(min(answers))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	(codd, ceven) = (0, 0)
	for i in range(n):
		diff = m - a[i]
		if diff % 2 == 1:
			codd += 1
		ceven += diff // 2
	ans = 10 ** 18
	diff = max(0, (ceven - codd - 1) // 3)
	codd += 2 * diff
	ceven -= diff
	ans = min(ans, max(ceven * 2, codd * 2 - 1))
	if ceven > 0:
		codd += 2
		ceven -= 1
		ans = min(ans, max(ceven * 2, codd * 2 - 1))
	m = max(a) + 1
	(codd, ceven) = (0, 0)
	for i in range(n):
		diff = m - a[i]
		if diff % 2 == 1:
			codd += 1
		ceven += diff // 2
	ans2 = 10 ** 18
	diff = max(0, (ceven - codd - 1) // 3)
	codd += 2 * diff
	ceven -= diff
	ans2 = min(ans2, max(ceven * 2, codd * 2 - 1))
	if ceven > 0:
		codd += 2
		ceven -= 1
		ans2 = min(ans2, max(ceven * 2, codd * 2 - 1))
	print(min(ans, ans2))


T = int(input())
while T:
	T -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	mx = max(a)
	ans = int(1e+18)
	for m in {mx, mx + 1}:
		ans1 = 0
		ans2 = 0
		for i in range(len(a)):
			d = m - a[i]
			ans2 += d // 2
			ans1 += d % 2
		if ans2 > ans1:
			dif = (ans2 - ans1) // 3
			ans1 += dif * 2
			ans2 -= dif
		ans = min(ans, max(ans2 * 2, ans1 * 2 - 1))
		if ans2 > 0:
			ans2 -= 1
			ans1 += 2
			ans = min(ans, max(ans2 * 2, ans1 * 2 - 1))
	print(ans)


for i in range(int(input())):
	a = int(input())
	b = [*map(int, input().split())]
	b.sort()
	c = []
	for i in range(len(b) - 1):
		y = b[-1] - b[i]
		c.append(y)
	t = c.count(0)
	for u in range(t):
		c.remove(0)
	even = 0
	odd = 0
	for j in range(len(c)):
		even += c[j] // 2
		odd += c[j] % 2
	if odd > even:
		ans = 2 * odd - 1
	else:
		x = even - odd
		if x % 3 == 0 or x % 3 == 1:
			ans = 2 * (even - x // 3)
		else:
			ans = 2 * (even - x // 3 - 1) + 1
	d = []
	for k in range(len(b)):
		z = b[-1] + 1 - b[k]
		d.append(z)
	even1 = 0
	odd1 = 0
	for l in range(len(d)):
		even1 += d[l] // 2
		odd1 += d[l] % 2
	if odd1 > even1:
		ans1 = 2 * odd1 - 1
	else:
		y = even1 - odd1
		if y % 3 == 0 or y % 3 == 1:
			ans1 = 2 * (even1 - y // 3)
		else:
			ans1 = 2 * (even1 - y // 3 - 1) + 1
	if ans > ans1:
		print(ans1)
	else:
		print(ans)


def solveByMe():
	n = int(input())
	lis = [int(i) for i in input().split()]
	mx = max(lis)
	res = pow(10, 18)
	for h in range(mx, mx + 4):
		one = two = 0
		for i in range(n):
			two += (h - lis[i]) // 2
			one += (h - lis[i]) % 2
		al = one + two * 2
		days = al // 3 * 2
		if al % 3 == 1:
			days += 1
		if al % 3 == 2:
			days += 2
		res = min(res, max(one * 2 - 1, days))
	print(res)
tt = int(input())
while tt:
	tt -= 1
	solveByMe()


def find(b, x):
	v = [0, 0]
	a = []
	for i in range(len(b)):
		if x - b[i] > 0:
			a.append(x - b[i])
	for i in range(len(a)):
		v[1] += a[i] // 2
		if a[i] % 2:
			v[0] += 1
	ans = 0
	if v[0] > v[1]:
		ans = 2 * v[1]
		v[0] -= v[1]
		v[0] -= 1
		ans += 1
		ans += 2 * v[0]
	elif v[1] == v[0] + 1:
		ans = 2 * (v[0] + 1)
	elif v[0] == v[1]:
		ans = 2 * v[0]
	else:
		ans += 2 * v[0]
		v[1] -= v[0]
		v[0] = 0
		x = v[1] // 3
		ans += 4 * x
		v[1] = v[1] % 3
		if v[1] == 1:
			ans += 2
		elif v[1] == 2:
			ans += 3
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = max(a)
	print(min(find(a, x), find(a, x + 1), find(a, x + 2)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	ans = 1e+18
	for jj in range(m, m + 4):
		(x, y) = (0, 0)
		for kk in a:
			x += (jj - kk) % 2
			y += (jj - kk) // 2
		ans = min(max((x + y * 2) // 3 * 2 + (x + y * 2) % 3, x * 2 - 1), ans)
	print(ans)


t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	mx = max(a)
	res = 1e+18
	h = mx
	while h <= mx + 3:
		two = 0
		one = 0
		for x in a:
			two += (h - x) // 2
			one += (h - x) % 2
		all = one + two * 2
		days = all // 3 * 2
		if all % 3 == 1:
			days += 1
		if all % 3 == 2:
			days += 2
		res = min(res, max(one * 2 - 1, days))
		h += 1
	print(res)
	t -= 1


import math
for i in range(int(input())):
	n = int(input())
	H = [int(k) for k in input().split()]
	a = max(H)
	b = max(H)
	MAX = 1e+18
	while a <= b + 3:
		t = 0
		o = 0
		for x in H:
			t += (a - x) // 2
			o += (a - x) % 2
		T = o + t * 2
		days = T // 3 * 2
		if T % 3 == 1:
			days += 1
		if T % 3 == 2:
			days += 2
		MAX = min(MAX, max(o * 2 - 1, days))
		a += 1
	print(MAX)


import math
for i in range(int(input())):
	n = int(input())
	h = [int(k) for k in input().split()]
	h.sort()
	MAX = 1e+18
	a = h[-1]
	b = []
	for j in range(4):
		a += j
		t = 0
		c = 0
		for k in range(n):
			t += (a - h[k]) // 2
			c += (a - h[k]) % 2
		T = t * 2 + c
		totald = T // 3 * 2
		if T % 3 == 1:
			totald += 1
		if T % 3 == 2:
			totald += 2
		MAX = min(MAX, max(c * 2 - 1, totald))
	print(MAX)


t = int(input())

def solve(n: int, h: list) -> None:
	mx = max(h)

	def find(target: int) -> int:
		(two, one, d) = (0, 0, 0)
		for x in h:
			if target - x == 1:
				one += 1
				d += 1
			else:
				two += (target - x) // 2
				one += target - x & 1
		ans = 0
		if one > two:
			ans = one * 2 - 1
		elif two > one:
			(left, right) = (0, two - one)
			while left <= right:
				mid = (left + right) // 2
				if one + mid * 2 <= two - mid + 1:
					left = mid + 1
				else:
					right = mid - 1
			ans = max((two - right) * 2, (one + 2 * right) * 2 - 1)
		else:
			ans = two * 2
		return ans
	print(min(find(mx), find(mx + 1)))
while t > 0:
	n = int(input())
	h = list(map(int, input().split()))
	solve(n, h)
	t -= 1


import math
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split(' ')))
	max_h = max(h)
	odd0 = 0
	odd1 = 0
	even0 = 0
	even1 = 0
	l = 0
	u = 0
	for hi in h:
		diff = max_h - hi
		l += diff // 2
		u += diff * 2
		if diff % 2 == 0:
			even0 += diff / 2
			even1 += diff / 2
			odd1 += 1
		else:
			odd0 += 1
			even0 += int((diff - 1) / 2)
			even1 += int((diff + 1) / 2)
	while l <= u:
		inter = int((l + u) / 2)
		if math.ceil(inter / 2) >= odd0 and math.floor(inter / 2) * 2 + math.ceil(inter / 2) - odd0 >= even0 * 2 or (math.ceil(inter / 2) >= odd1 and math.floor(inter / 2) * 2 + math.ceil(inter / 2) - odd1 >= even1 * 2):
			u = inter - 1
		else:
			l = inter + 1
	print(l)