Chef gets confused between mean and median very often, and as a result, he has developed a dislike of arrays whose mean and median are not equal.

Chef has an array A of N elements. He can perform the following operation on it:
Pick an index 1 ≤ i ≤ N and increase A_{i} by 1.

He would like to obtain an array whose mean and median are equal. Determine the minimum number of operations required to achieve this.

Note: The median of an array A of length N is defined as follows:
Sort the array A. Then, 
If N is even, the median is the (\frac{N}{2})^{\text{th}} element
If N is odd, the median is the (\frac{N + 1}{2})^{\text{th}} element

For example, the median of the array [3,4,1,2] is 2 and the median of the array [3,4,1] is 3.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of testcases. The description of T test cases follows.
- The first line of each test case contains a single integer N, denoting the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case, print a single line containing one integer — the minimum number of operations Chef needs to perform to make the mean and median equal.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 3 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
3
1 2 3
4
1 1 3 3
5
1 1000000000 1 1000000000 1

----- Sample Output 1 ------ 
0
4
500000002

----- explanation 1 ------ 
Test Case $1$: The mean and median of the array are both $2$. They are already equal, so no operations are required.

Test Case $2$: It is optimal to apply the operation on $1^{st}$ and $2^{nd}$ index twice each. The array after applying these operations will be $[3, 3, 3, 3]$, which has both mean and median $3$.

Difficulty: VERY_HARD
Tags: Sorting

Data structures

Mathematics

Complete search
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
def check(arr, mean, n):
	sum = 0
	for i in range(len(arr)):
		sum += arr[i]
	allowed_operations = n * mean - sum
	if allowed_operations < 0:
		return -1
	required_operations = 0
	for i in range((n - 1) // 2, n):
		required_operations += max(0, mean - arr[i])
	if required_operations > allowed_operations:
		return -1
	else:
		return allowed_operations
for i in range(int(input())):
	N = int(input())
	arr = [int(x) for x in input().split()]
	arr = sorted(arr)
	l = arr[(len(arr) - 1) // 2]
	r = arr[len(arr) - 1]
	ans = -1
	n = len(arr)
	while l <= r:
		mid = (l + r) // 2
		minOp = check(arr, mid, n)
		if minOp != -1:
			ans = minOp
			r = mid - 1
		else:
			l = mid + 1
	print(ans)


def check_mean_median(arr, n, x):
	cost_mean = n * x - sum(arr)
	if cost_mean < 0:
		return -1
	cost_median = 0
	for i in range((n - 1) // 2, n):
		cost_median += max(0, x - arr[i])
	if cost_median > cost_mean:
		return -1
	else:
		return cost_mean

def solve(arr, n):
	arr.sort()
	(low, high, ans) = (arr[(n - 1) // 2], 10 ** 9 + 10, -1)
	while low <= high:
		mid = low + (high - low) // 2
		min_oper = check_mean_median(arr, n, mid)
		if min_oper != -1:
			ans = min_oper
			high = mid - 1
		else:
			low = mid + 1
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr, n)


def snek(a, n, x):
	c = n * x - sum(a)
	if c < 0:
		return -1
	c2 = 0
	for i in range((n - 1) // 2, n):
		c2 += max(0, x - a[i])
	if c2 > c:
		return -1
	else:
		return c
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(l, h, ans) = (a[(n - 1) // 2], 10 ** 9 + 10, -1)
	while l <= h:
		m1 = l + (h - l) // 2
		m2 = snek(a, n, m1)
		if m2 != -1:
			ans = m2
			h = m1 - 1
		else:
			l = m1 + 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	mod_in = (n - 1) // 2
	l = a[mod_in] - 1
	r = 10 ** 9
	while r - l > 1:
		cur = (l + r) // 2
		meanop = cur * n - sum(a)
		medianop = 0
		for i in range(mod_in, n):
			medianop += max(0, cur - a[i])
		if meanop >= medianop:
			r = cur
		else:
			l = cur
	print(r * n - sum(a))


import sys
int1 = lambda x: int(x) - 1
pDB = lambda *x: print(*x, end='\n', file=sys.stderr)
p2D = lambda x: print(*x, sep='\n', end='\n\n', file=sys.stderr)

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
inf = 18446744073709551615
md = 10 ** 9 + 7

def solve():

	def binary_search(l, r, ok, minimize):
		if minimize:
			l -= 1
		else:
			r += 1
		while l + 1 < r:
			m = (l + r) // 2
			if ok(m) ^ minimize:
				l = m
			else:
				r = m
		if minimize:
			return r
		return l

	def ok(v):
		if v * n < s:
			return False
		t = v * n
		for i in range(mid, n):
			t -= max(v, aa[i])
		return t >= pre
	n = II()
	aa = LI()
	mid = (n - 1) // 2
	aa.sort()
	pre = sum(aa[:mid])
	s = sum(aa)
	m = aa[mid]
	v = binary_search(m, 10 ** 9 + 5, ok, True)
	ans = v * n - s
	print(ans)
for _ in range(II()):
	solve()


def check(A, N, x):
	mean_op = N * x - sum(A)
	if mean_op < 0:
		return -1
	median_op = 0
	for i in range((N - 1) // 2, N):
		median_op += max(0, x - A[i])
	if median_op <= mean_op:
		return mean_op
	else:
		return -1

def solve(A, N):
	A.sort()
	low = A[(N - 1) // 2]
	high = 10 ** 9 + 10
	ans = -1
	while low <= high:
		mid = low + (high - low) // 2
		min_operations = check(A, N, mid)
		if min_operations == -1:
			low = mid + 1
		else:
			high = mid - 1
			ans = min_operations
	print(ans)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	solve(A, N)


def cal(arr, n, med):
	ind = n // 2 - 1 if n % 2 == 0 else (n + 1) // 2 - 1
	c = 0
	for i in range(ind, n):
		if i == ind:
			c += med - arr[ind]
			arr[ind] = med
		elif arr[i - 1] > arr[i]:
			c += arr[i - 1] - arr[i]
			arr[i] = arr[i - 1]
	tot = sum(arr)
	if tot > med * n:
		return -1
	else:
		return c + (med * n - tot)
for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	tot = sum(arr)
	median = arr[n // 2 - 1] if n % 2 == 0 else arr[(n + 1) // 2 - 1]
	if tot == median * n:
		print(0)
	elif tot < median * n:
		print(median * n - tot)
	else:
		l = median + 1
		h = 10 ** 9 + 1
		fc = 10 ** 18
		while l <= h:
			mid = (l + h) // 2
			cost = cal(arr[:], n, mid)
			if cost == -1:
				l = mid + 1
			else:
				fc = min(fc, cost)
				h = mid - 1
		print(fc)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def hnbhai(tc):
	n = sb()
	a = sd()
	a.sort()
	m = (n - 1) // 2
	sm = sum(a)
	avg = sm / n
	ans = float('inf')
	low = a[m]
	high = 10 ** 15
	while low <= high:
		mid = (low + high) // 2
		left = n * mid - sm
		for i in range(m, n):
			if a[i] < mid:
				left -= mid - a[i]
		if left >= 0:
			ans = n * mid - sm
			high = mid - 1
		else:
			low = mid + 1
	print(ans)
	return
for _ in range(sb()):
	hnbhai(_ + 1)


def check(a, n, k):
	meanop = n * k - sum(a)
	if meanop < 0:
		return -1
	medianop = 0
	for i in range((n - 1) // 2, n):
		medianop += max(0, k - a[i])
	if medianop > meanop:
		return -1
	return meanop

def solve(a, n):
	a.sort()
	(low, high, ans) = (a[(n - 1) // 2], 10 ** 9 + 10, -1)
	while low <= high:
		k = low + (high - low) // 2
		op = check(a, n, k)
		if op != -1:
			ans = op
			high = k - 1
		else:
			low = k + 1
	print(ans)
T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	solve(a, n)


import sys
input = sys.stdin.readline

def feasible(arr, tar, total):
	N = len(arr)
	meanop = N * tar - total
	medianop = 0
	for i in range((N - 1) // 2, N):
		medianop += max(0, tar - arr[i])
	if meanop >= medianop:
		return meanop
	return -1
t = int(input())
for case in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	l = A[(n - 1) // 2]
	r = 10 ** 9
	total = sum(A)
	while l <= r:
		mid = (l + r) // 2
		res = feasible(A, mid, total)
		if res != -1:
			r = mid - 1
			ans = res
		else:
			l = mid + 1
	print(ans)


import sys
input = sys.stdin.readline

def valid(k, arr, total):
	mean_op = k * len(arr) - total
	median_op = 0
	n = len(arr)
	for i in range((n - 1) // 2, n):
		median_op += max(0, k - arr[i])
	if mean_op >= median_op:
		return mean_op
	return -1
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	low = arr[(n - 1) // 2]
	high = 10 ** 9
	ans = -1
	total = sum(arr)
	while low <= high:
		mid = low + (high - low) // 2
		status = valid(mid, arr, total)
		if status != -1:
			ans = status
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


def findMedian(A):
	return A[(len(A) - 1) // 2]

def isX(A, X):
	summ = 0
	for i in range(len(A)):
		if i < (len(A) - 1) // 2:
			summ += A[i]
		else:
			summ += max(X, A[i])
	return summ <= len(A) * X
for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	sumA = sum(A)
	originalMedian = findMedian(A)
	if originalMedian * N >= sumA:
		print(originalMedian * N - sumA)
	else:
		l = int(originalMedian)
		r = max(A)
		while r - l > 1:
			mid = (l + r) // 2
			if isX(A, mid):
				r = int(mid)
			else:
				l = int(mid)
		print(r * N - sumA)


from math import ceil

def is_feasible(ans, arr):
	n = len(arr)
	median_pos = n // 2
	if n % 2 == 0:
		median_pos -= 1
	if arr[median_pos] > ans:
		return False
	req = n * ans - sum(arr)
	moves = 0
	for i in range(median_pos, len(arr)):
		if arr[i] < ans:
			moves += ans - arr[i]
	if moves > req:
		return False
	return True
for _ in range(int(input())):
	n = int(input())
	MAX = 10 ** 9 + 1
	arr = list(sorted(map(int, input().split())))
	l = 0
	fin_ans = MAX
	while l <= MAX:
		ans = (l + MAX) // 2
		if is_feasible(ans, arr):
			fin_ans = min(fin_ans, ans)
			MAX = ans - 1
		else:
			l = ans + 1
	print(n * fin_ans - sum(arr))


def check(arr, s, n, x):
	op1 = x * n - s
	if op1 < 0:
		return -1
	op2 = 0
	for i in range((n - 1) // 2, n):
		op2 += max(x - arr[i], 0)
	if op2 > op1:
		return -1
	return op1
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	s = sum(arr)
	(low, high) = (arr[(n - 1) // 2], 10 ** 9)
	ans = 0
	while low <= high:
		md = (low + high) // 2
		val = check(arr, s, n, md)
		if val != -1:
			ans = val
			high = md - 1
		else:
			low = md + 1
	print(ans)


def check(A, N, x):
	meanop = N * x - sum(A)
	if meanop < 0:
		return -1
	medianop = 0
	for i in range((N - 1) // 2, N):
		medianop += max(0, x - A[i])
	if medianop > meanop:
		return -1
	return meanop

def solve(A, N):
	A.sort()
	(low, high, ans) = (A[(N - 1) // 2], 10 ** 9 + 10, -1)
	while low <= high:
		mid = low + (high - low) // 2
		minop = check(A, N, mid)
		if minop != -1:
			ans = minop
			high = mid - 1
		else:
			low = mid + 1
	print(ans)
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	solve(A, N)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	s = sum(A)
	low = A[(n - 1) // 2]
	high = 10 ** 9
	ans = 10 ** 9
	while low <= high:
		k = (low + high) // 2
		mean = k * n - s
		median = 0
		for i in range((n - 1) // 2, n):
			median += max(0, k - A[i])
		if mean >= median:
			ans = mean
			high = k - 1
		else:
			low = k + 1
	print(ans)


import math

def check(mean):
	req_op = mean * n - s
	idx = (n - 1) // 2
	if l[idx] > mean:
		return False
	r = mean - l[idx]
	for i in range(idx + 1, n):
		if l[i] < mean:
			r += mean - l[i]
	return r <= req_op
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	s = sum(l)
	res = 10 ** 18
	low = 1
	high = 10 ** 24
	while low <= high:
		mid = (low + high) // 2
		if check(mid):
			res = min(res, mid * n - s)
			high = mid - 1
		else:
			low = mid + 1
	print(res)


from bisect import bisect
for tcase in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	s = [0]
	for x in a:
		s.append(s[-1] + x)
	im = (n - 1) // 2
	(l, r) = (a[im], a[n - 1])
	while l < r:
		m = (l + r) // 2
		i = bisect(a, m)
		x = m * (i - im) - (s[i] - s[im])
		if m * n < s[n] + x:
			l = m + 1
		else:
			r = m
	print(l * n - s[n])


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	arr.sort()
	s = sum(arr)
	mean = s / n
	med = arr[(n - 1) // 2]
	if med == mean:
		print(0)
		continue

	def check(k):
		meanop = k * n - s
		medop = 0
		for i in range((n - 1) // 2, n):
			if arr[i] < k:
				medop += k - arr[i]
			else:
				break
		if meanop >= medop:
			return meanop
		return -1
	l = med
	h = arr[-1]
	ans = 0
	while l <= h:
		mid = l + (h - l) // 2
		a = check(mid)
		if a == -1:
			l = mid + 1
		else:
			ans = a
			h = mid - 1
	print(ans)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	idx = (n - 1) // 2
	s = 0
	for i in range(n):
		s += arr[i] - arr[idx]
	if s <= 0:
		print(abs(s))
	else:
		x = sum(arr)
		low = 0
		high = 10 ** 9 + 1
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			s = 0
			for el in arr[idx:]:
				s += max(0, mid - el)
			if arr[idx] <= mid and s <= mid * n - x:
				ans = mid * n - x
				high = mid - 1
			else:
				low = mid + 1
		print(ans)


def check(mean):
	req_op = mean * n - cur_sum
	idx = (n - 1) // 2
	if a[idx] > mean:
		return False
	r = mean - a[idx]
	for i in range(idx + 1, n):
		if a[i] < mean:
			r += mean - a[i]
	return r <= req_op
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	cur_sum = sum(a)
	ans = 10 ** 18
	(low, high) = (1, 10 ** 24)
	while low <= high:
		mid = (low + high) // 2
		if check(mid):
			ans = min(ans, mid * n - cur_sum)
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


from sys import stdin
input = stdin.readline

def check(x):
	ans = 0
	for i in range(middle, n):
		ans += max(0, x - a[i])
	if n * x < s + ans:
		return -1
	return n * x - (s + ans) + ans

def answer():
	s = sum(a)
	(l, h) = (a[middle], a[-1])
	while l <= h:
		mid = (l + h) // 2
		value = check(mid)
		if value != -1:
			ans = value
			h = mid - 1
		else:
			l = mid + 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	s = sum(a)
	middle = n // 2
	if n & 1 == 0:
		middle -= 1
	print(answer())


def possible(rmd):
	rs = n * rmd
	cs = s
	for j in range(md, n):
		cs += max(rmd - a[j], 0)
	if rs < cs:
		return (False, -1)
	return (True, rs - s)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	a.sort()
	ans = float('inf')
	if n & 1:
		md = n // 2
	else:
		md = n // 2 - 1
	md2 = s // n
	mod = s % n
	if mod != 0:
		md2 += 1
	l = max(a[md], md2)
	r = a[-1]
	p = 0
	while l <= r:
		mid = l + (r - l) // 2
		check = possible(mid)
		if check[0]:
			if ans > check[1]:
				ans = check[1]
				p = mid
			r = mid - 1
		else:
			l = mid + 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')

def solve():

	def check(a, b):
		if l[n // 2 - (n % 2 == 0)] > a:
			return False
		for i in range(n // 2 - (n % 2 == 0), n):
			if l[i] < a:
				need = a - l[i]
				if need > b:
					return False
				b -= need
			else:
				return True
		return b >= 0
	n = inp()
	l = li()
	s = sum(l)
	l.sort()
	if s % n == 0 and l[n // 2 - (n % 2 == 0)] == s // n:
		print(0)
		return
	low = 1
	ans = 0
	high = mod * mod
	S = s
	s = n - s % n
	while low <= high:
		mid = (low + high) // 2
		new_s = mid * n
		if new_s < S:
			low = mid + 1
			continue
		median = mid
		temp = new_s - S
		if check(median, temp):
			ans = temp
			high = mid - 1
		else:
			low = mid + 1
	pr(ans)
for _ in range(inp()):
	solve()


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353
for _ in range(ii()):
	n = ii()
	a = il()
	a.sort()
	x = a[n // 2 - (1 - n % 2)]
	y = sum(a) / n
	if x == y:
		print(0)
		continue
	if y < x:
		print(x * n - sum(a))
		continue
	l = 1
	h = 10 ** 15
	s = sum(a)
	b = [0 for i in range(n)]
	ans = -1
	while l <= h:
		m = (l + h) // 2
		t1 = m * n - s
		t = 0
		for i in range(n // 2 - (1 - n % 2), n):
			if a[i] < m:
				t += m - a[i]
		if t <= t1:
			ans = t1
			h = m - 1
		else:
			l = m + 1
	print(ans)