There is a town with N people and initially, the i^{th} person has A_{i} coins. However, some people of the town decide to become *monks*. If the i^{th} person becomes a monk, then:
He leaves the town thereby reducing the number of people in the town by 1.
He distributes X (0 ≤ X ≤ A_{i}) coins to the remaining people of the town (not necessarily equally). Note that each monk can freely choose his value of X, and different monks may choose different values of X.
He takes the remaining A_{i} - X coins with him.

For example, initially, if A = [1, 3, 4, 5] and 4^{th} person decides to become a monk then he can leave the town and can give 2 coins to the 1^{st} person, 1 coin to the 2^{nd} person, no coins to the 3^{rd} person and take 2 coins along with him while going. Now A becomes [3, 4, 4].

Determine the minimum number of people who have to become monks, so that in the end, everyone remaining in the town has an equal number of coins.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the number of people in the town.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} denoting the initial number of coins of everyone in the town.

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

For each test case, output the minimum number of people who have to become monks, so that in the end, everyone remaining in the town has an equal number of coins.

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

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

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

----- Sample Output 1 ------ 
0
1
2

----- explanation 1 ------ 
Test case $1$: All the people already have an equal number of coins.

Test case $2$: The $2^{nd}$ person can become a monk and give his $1$ coin to the person with $4$ coins. After this, both the remaining people will have $5$ coins.

Test case $3$: One way of two people becoming monks is as follows:
- The $2^{nd}$ person becomes a monk, and takes his $1$ coin with him
- The $3^{rd}$ person becomes a monk, and gives one coin each to the $4^{th}$ and $5^{th}$ people

Everyone remaining in the town now has $2$ coins.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if len(a) == 1:
		print(0)
		continue
	s = sum(a)
	c = 0
	ans = -1
	for i in range(0, n):
		c += a[i]
		if a[i] * (i + 1) - c <= s - c:
			ans = i
	print(n - ans - 1)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	ps = []
	ss = []
	s = 0
	for i in a:
		s += i
		ps.append(s)
	s1 = 0
	for i in a[::-1]:
		s1 += i
		ss.append(s1)
	ss = ss[::-1]
	r = set(a)
	if len(r) == 1:
		print(0)
	else:
		for i in range(n - 2, -1, -1):
			if ps[i] < (i + 1) * a[i]:
				if ps[i] + ss[i + 1] >= (i + 1) * a[i]:
					print(n - 1 - i)
					break
			else:
				print(n - 1 - i)
				break


for _ in range(int(input())):
	n = int(input())
	lst = sorted(list(map(int, input().split())))
	total = 0
	for l in lst:
		total += l
	ans = 0
	for c in range(n):
		if total / (n - c) >= lst[n - c - 1]:
			ans = c
			break
	print(ans)


T = int(input())
Coins = list()
Res = list()
for i in range(T):
	N = int(input())
	Coins = input().split(' ')
	A = list()
	n = 0
	while n < N:
		A = list()
		A.append(int(Coins[n]))
		n = n + 1
	Coins = [int(j) for j in Coins]
	Coins.sort()
	SumOfCoins = sum(Coins)
	n = N
	res = 0
	for k in range(n):
		if Coins[k] * (k + 1) <= SumOfCoins:
			res = n - k - 1
	Res.append(res)
for i in Res:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = False
	count = 0
	k = 0
	a.sort()
	if a[0] == a[-1]:
		print(0)
	else:
		b = [0] * (n + 1)
		for i in range(0, n):
			b[i + 1] = b[i] + a[i]
		while c == False:
			k += a[-1]
			a.pop()
			b.pop()
			count += 1
			if k >= (n - count) * a[-1] - b[-1]:
				c = True
		print(count)


a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	q = sum(A)
	x = 1
	p = 0
	if A.count(A[0]) == N:
		x = 0
	else:
		for j in range(N - 1, 0, -1):
			p += A[j]
			if p >= A[j - 1] * j - (q - p):
				break
			else:
				x += 1
	print(x)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	summ = sum(a)
	for i in range(n - 1, -1, -1):
		if a[i] * (i + 1) <= summ:
			print(n - (i + 1))
			break


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	s = sum(a)
	for i in range(n):
		if a[i] * (n - i) <= s:
			print(i)
			break


m = int(input())
r = [0] * m
for i in range(m):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = [0] * n
	for j in range(1, n):
		b[j] = (a[j] - a[j - 1]) * j + b[j - 1]
	t = 0
	j = n - 1
	while t < b[j]:
		t = t + a[j]
		j = j - 1
	r[i] = n - 1 - j
	print(r[i])


tc = int(input())
for TC in range(tc):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	dup = [0]
	for i in range(1, n):
		dup.append(dup[i - 1] + (l[i] - l[i - 1]) * i)
	prev = 0
	ans = 0
	if dup[-1] == 0:
		ans = 0
	else:
		prev = l[-1]
		ans += 1
		for i in range(n - 2, -1, -1):
			if dup[i] <= prev:
				break
			ans += 1
			prev += l[i]
	print(ans)


ans = []
for _ in range(int(input())):
	N = int(input())
	A = sorted([int(x) for x in input().split()], reverse=True)
	sm = sum(A)
	for i in range(N):
		if A[i] * (N - i) <= sm:
			break
	ans.append(i)
print(*ans, sep='\n')


for _ in range(int(input())):
	initial_pop = int(input())
	coins = [int(num) for num in input().split()]
	coins.sort()
	coins_sum = sum(coins)
	for current_pop in range(initial_pop, 0, -1):
		coins_current = coins[current_pop - 1]
		if coins_current == coins[0] or coins_current <= coins_sum // current_pop:
			print(initial_pop - current_pop)
			break


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	(req, avail, ans) = (0, 0, 0)
	for i in range(n):
		req += l[0] - l[i]
	if req == 0:
		ans = 0
	else:
		for i in range(1, n):
			avail += l[i - 1]
			req -= (n - i) * (l[i - 1] - l[i])
			if avail >= req:
				ans = i
				break
	print(ans)


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	k1 = list(k)
	k1.sort(reverse=True)
	sk = 0
	for j in k1:
		sk += j
	sk2 = sk
	if k1[0] == k1[-1]:
		print(0)
		continue
	b = k1[0]
	for j in range(0, n - 1):
		b += k1[j + 1]
		if b >= (n - j - 1) * k1[j + 1] - (sk - b):
			print(j + 1)
			break


def qsort(inlist):
	if inlist == []:
		return []
	else:
		pivot = inlist[0]
		lesser = qsort([x for x in inlist[1:] if x < pivot])
		greater = qsort([x for x in inlist[1:] if x >= pivot])
		return lesser + [pivot] + greater
for t in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	a = s[0]
	b = s.count(a)
	c = 1
	if b == n:
		print(0)
	elif b == n - 1:
		print(1)
	else:
		m = 0
		s.sort(reverse=True)
		i = 0
		p = sum(s)
		while 1:
			m += s[0]
			p -= s[0]
			s.remove(s[0])
			n -= 1
			i += 1
			if m >= n * s[0] - p:
				break
			else:
				c += 1
		print(c)
	t -= 1


t = int(input())
for _ in range(t):
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	if A.count(max(A)) == len(A):
		print(0)
		continue
	sm = sum(A)
	A.sort()
	(curr, ans) = (0, N)
	for i in range(N):
		curr += A[i]
		x = sm - curr
		if x >= A[i] * (i + 1) - curr:
			ans = min(ans, N - i - 1)
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	if A[0] == A[-1]:
		print(0)
		continue
	total = sum(A)
	for (i, a) in enumerate(A[:-1]):
		if A[i + 1] == A[-1]:
			print(i + 1)
			break
		if total / (N - i - 1) >= A[i + 1]:
			print(i + 1)
			break


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	s = sum(a)
	if a[0] == a[-1]:
		print(0)
		continue
	for i in range(n):
		if a[i + 1] * (n - i - 1) - s <= 0:
			print(i + 1)
			break


import sys
from collections import Counter, defaultdict, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

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

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	a = li()
	a.sort(reverse=True)
	total = sum(a)
	for i in range(n):
		if total >= a[i] * (n - i):
			print(i)
			break


t = int(input())
for test in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	total = sum(A)
	A.sort(reverse=True)
	for i in range(N):
		if total >= A[i] * (N - i):
			print(i)
			break


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()

def solve():
	n = ri()
	a = rl()
	s = sum(a)
	a.sort(reverse=True)
	ans = 0
	for i in range(n):
		if s >= a[i] * (n - i):
			ans = i
			break
	return ans

def main():
	for _ in range(ri()):
		print(solve())
main()


T = int(input())
while T > 0:
	n = input()
	a = [int(x) for x in input().split()]
	t = 1
	suma = 0
	a = sorted(a)
	for i in a:
		suma += i
	suma -= a[-1]
	if a[0] == a[-1]:
		print(0)
	else:
		while (len(a) - 1) * a[-2] - suma > a[-1]:
			suma -= a[-2]
			sa = a.pop(-1)
			a[-1] += sa
			t += 1
		print(t)
	T -= 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) == 1:
		print('0')
	else:
		add = sum(a)
		a.sort()
		big = 0
		ans = n
		while True:
			big += a.pop()
			ans -= 1
			if add - big >= a[-1] * ans - big:
				print(n - ans)
				break


import math
n = int(input())
from collections import Counter
for _ in range(n):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	totalSum = sum(A)
	maxSoFar = 0
	if len(set(A)) == 1:
		print(0)
	else:
		for i in range(N):
			maxSoFar = max(maxSoFar, A[i])
			if maxSoFar * (i + 1) > totalSum:
				print(N - i)
				break


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()

def solve():
	N = ri()
	A = rl()
	ans = N - 1
	s = sum(A)
	A.sort()
	if A[0] == A[N - 1]:
		return 0
	cur = 0
	for i in range(N):
		cur += A[i]
		x = s - cur
		if x >= A[i] * (i + 1) - cur:
			ans = min(ans, N - i - 1)
	return ans

def main():
	for _ in range(ri()):
		print(solve())
main()


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = 1
	sa = 0
	sl = sum(a) - a[0]
	c = n - 1
	while i < n:
		sa += i * (a[i] - a[i - 1])
		sl -= a[i]
		if sa <= sl:
			c = min(c, n - i - 1)
		else:
			k = 0
			d = sa - sl
			k = math.ceil(d / a[i])
			c = min(c, k + n - i)
		i += 1
	print(c)


def checker(arr, k):
	t = sum(arr[0:k])
	i = k
	req = 0
	target = arr[i]
	while i < len(arr):
		req += target - arr[i]
		i += 1
	if req <= t:
		return 1
	else:
		return 0

def ans(arr):
	start = 0
	end = len(arr)
	temp = sorted(arr, reverse=True)
	c = 0
	while start <= end:
		mid = (start + end) // 2
		if checker(temp, mid) == 1:
			c = mid
			end = mid - 1
		else:
			start = mid + 1
	return c
test_cases = int(input())
while test_cases != 0:
	d_ = input()
	d = list(map(int, input().split()))
	print(ans(d))
	test_cases -= 1


t = int(input())
for i in range(t):
	l = int(input())
	arr = list(map(int, input().split()))
	if l == 1:
		print(0)
	else:
		arr.sort()
		s = sum(arr)
		target = 0
		for i in range(l - 1, -1, -1):
			temp = (i + 1) * arr[i] - s
			if target >= temp:
				break
			target += arr[i]
			s -= arr[i]
		print(l - i - 1)


t = int(input())
for i in range(t):
	l = int(input())
	arr = list(map(int, input().split()))
	if l == 1:
		print(0)
	else:
		arr.sort()
		prev = [0 for i in range(l)]
		prev[l - 1] = 0
		for i in range(l - 2, -1, -1):
			prev[i] = arr[i + 1] + prev[i + 1]
		total = 0
		for i in range(1, l):
			if arr[i] != arr[i - 1]:
				total += i * (arr[i] - arr[i - 1])
			if total >= prev[i]:
				break
		if total == 0:
			print(0)
		elif total == prev[i]:
			print(l - i - 1)
		else:
			print(l - i)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	h = 0
	for i in a:
		h += i
	summ = 0
	ans = 0
	t = n - 1
	while summ < n * a[n - 1] - h:
		summ += a[t]
		n = n - 1
		h -= a[t]
		ans += 1
		t -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)[::-1]
	if 1 == len(set(l)):
		print(0)
	else:
		mid = n // 2
		le = 0
		ri = n
		while mid != le and mid != ri:
			if sum(l[:mid]) >= (n - mid) * l[mid] - sum(l[mid:n]):
				ri = mid
				mid = (mid + le) // 2
			else:
				le = mid
				mid = (mid + ri) // 2
		if sum(l[:mid]) >= (n - mid) * l[mid] - sum(l[mid:n]):
			print(mid)
		else:
			print(mid + 1)


for M in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	s = sum(arr)
	if max(arr) == min(arr):
		print(0)
		continue
	for i in range(n - 1):
		if s >= (n - 1 - i) * arr[i + 1]:
			print(i + 1)
			break


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	l.sort(reverse=True)
	if l[0] == l[-1]:
		print('0')
	else:
		for i in range(0, n - 1):
			if l[i + 1] * (n - 1 - i) - s <= 0:
				print(i + 1)
				break


from collections import Counter
from itertools import accumulate
from math import ceil

def solve():
	if n == 1:
		return 0
	c = Counter(a)
	if len(c) == 1:
		return 0
	a.sort(reverse=True)
	ar = a.copy()
	ar.reverse()
	ca = list(accumulate(a))
	cr = list(accumulate(ar))
	cr.reverse()
	for i in range(1, n):
		f = a[i] * (n - i) - cr[i]
		if ca[i - 1] >= f:
			return i
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	narr = arr.copy()
	narr.sort(reverse=True)
	pref_sum = 0
	suf_sum = [0 for i in range(n)]
	cs = 0
	for i in range(n - 1, -1, -1):
		cs += narr[i]
		suf_sum[i] = cs
	for i in range(n):
		if pref_sum >= narr[i] * (n - i) - suf_sum[i]:
			print(i)
			break
		pref_sum += narr[i]


t = int(input())
for _ in range(t):
	n = int(input())
	arr = sorted(list(map(int, input().split())), reverse=True)
	x = sum(arr)
	ans = 0
	d = 0
	for i in range(n):
		if arr[i] * (n - i) > x + d:
			ans += 1
			d += arr[i]
			x -= arr[i]
		else:
			break
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	if n == 1 or n == 0:
		coins = input()
		print(0)
		continue
	coins = [int(i) for i in input().split()]
	coins.sort(reverse=True)
	if coins[0] == coins[n - 1]:
		print(0)
		continue
	if n == 2:
		print(1)
		continue
	if n == 3:
		print(1)
		continue
	summ = sum(coins)
	summ -= coins[0]
	req = (n - 1) * coins[1] - summ
	monk_sum = coins[0]
	count = 1
	broke = 0
	i = 0
	for i in range(1, n - 1):
		if req <= monk_sum:
			break
		else:
			count += 1
			monk_sum += coins[i]
			summ -= coins[i]
			req = (n - i - 1) * coins[i + 1] - summ
	print(count)


import math
ans = []
nq = int(input())
for _ in range(nq):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	s = sum(A)
	if A[-1] == A[0]:
		val = 0
	else:
		for i in range(0, n - 1):
			if A[i + 1] * (n - 1 - i) <= s:
				val = i + 1
				break
	ans.append(val)
print(*ans, sep='\n')


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	P = 0
	RQ = A[0] * N - sum(A)
	AV = 0
	MK = 0
	if RQ > 0:
		for i in range(1, N):
			RQ -= (N - i) * (A[i - 1] - A[i])
			AV += A[i - 1]
			MK += 1
			if AV >= RQ:
				break
	print(MK)


def main():
	T = int(input())
	for i in range(T):
		ans = 0
		n = int(input())
		a = list(map(int, input().split()))
		a.sort(reverse=True)
		need = 0
		avail = a[0]
		if a[0] == a[-1]:
			print('0')
			continue
		if a[0] != a[-1] and n == 2:
			print('1')
			continue
		for i in range(1, n):
			need += a[1] - a[i]
		ans += 1
		if need <= avail:
			print('1')
			continue
		for i in range(1, n - 1):
			ans += 1
			avail += a[i]
			need += a[i + 1] * (n - i - 1) - a[i] * (n - i) + a[i]
			if avail >= need:
				break
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	r = n * a[0] - sum(a)
	g = 0
	if r == 0:
		print(0)
	else:
		w = 0
		for i in range(1, n):
			r -= (n - i) * (a[i - 1] - a[i])
			w += a[i - 1]
			if w >= r:
				g = i
				break
		print(g)


def check(l, s, n):
	if l[n - 1] * n == s:
		return True
	return False
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort()
	s = sum(l)
	ss = 0
	for i in range(n):
		if check(l, s, n - i):
			print(i)
			break
		if ss >= l[n - i - 1] * (n - i) - s:
			print(i)
			break
		ss += l[n - i - 1]
		s -= l[n - i - 1]


try:
	T = int(input())
	for k in range(T):
		N = int(input())
		A = list(map(int, input().split(' ')))
		A.sort()
		sum = 0
		for j in range(N):
			sum += A[j]
		if A[0] == A[N - 1]:
			print(0)
			continue
		ans = N
		C = 0
		for i in range(N):
			C += A[i]
			x = sum - C
			if x >= A[i] * (i + 1) - C:
				ans = min(ans, N - i - 1)
		print(ans)
except:
	pass


t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	if len(set(a)) == 1:
		print('0')
	else:
		add = sum(a)
		a.sort()
		ans = n
		while True:
			a.pop()
			ans -= 1
			if add >= a[-1] * ans:
				print(n - ans)
				break
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())), reverse=True)
	if l[0] == l[n - 1]:
		print(0)
	else:
		(b, a) = (sum(l), 0)
		for i in range(n):
			a += l[i]
			b -= l[i]
			if l[i + 1] * (n - 1 - i) <= b + a:
				print(i + 1)
				break


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort(reverse=True)
	(reqd, ans, avail) = (0, 0, 0)
	for i in range(n):
		reqd += lst[0] - lst[i]
	if reqd == 0:
		ans = 0
	else:
		for i in range(1, n):
			avail += lst[i - 1]
			reqd -= (n - i) * (lst[i - 1] - lst[i])
			if avail >= reqd:
				ans = i
				break
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	li = list(map(int, input().split()))
	li.sort(reverse=True)
	total_sum = sum(li)
	b_sum = 0
	c_sum = total_sum
	flag = 0
	for j in range(1, n):
		if li[j - 1] != li[j]:
			flag = 1
			break
	if flag == 0:
		print(0)
	else:
		for j in range(1, n):
			b_sum += li[j - 1]
			c_sum -= li[j - 1]
			temp = li[j] * (n - j) - c_sum
			if temp <= b_sum:
				print(j)
				break


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	diff = x = c = 0
	for i in range(n):
		diff += arr[-1] - arr[i]
	for i in range(n - 1, 0, -1):
		if x >= diff:
			break
		diff -= (arr[i] - arr[i - 1]) * i
		x += arr[i]
		c += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	prefix = [a[0]]
	for index in range(1, n):
		prefix.append(a[index] + prefix[-1])
	ans = 0
	added = 0
	for index in range(n - 1, 0, -1):
		val = a[index]
		total = prefix[index - 1]
		if index * val - added <= total:
			break
		added += val
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	a.sort()
	if a[0] == a[-1]:
		print(0)
	else:
		b = []
		b.append(0)
		for i in range(1, n - 1):
			b.append((a[i] - a[i - 1]) * i + b[i - 1])
		sum = a[n - 1]
		for i in range(n - 2, -1, -1):
			if sum >= b[i]:
				print(n - 1 - i)
				break
			sum = sum + a[i]


from collections import Counter
import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	d = Counter(l)
	for (i, key) in enumerate(d):
		l1.append((key, d[key]))
	l1.sort(reverse=True)
	m = l1[0][0]
	tot = 0
	count = 0
	count1 = 0
	for i in l1:
		tot += (m - i[0]) * i[1]
		count1 += i[1]
	for (i, item) in enumerate(l1):
		if tot <= m * item[1]:
			count += max(0, math.ceil(tot / m))
			break
		else:
			count1 -= item[1]
			tot = tot - m * item[1] - (item[0] - l1[i + 1][0]) * count1
			m = l1[i + 1][0]
			count += item[1]
	print(count)


def fun(n, a):
	a.sort(reverse=True)
	if a[0] == a[n - 1]:
		return 0
	i = 1
	s = sum(a)
	x = 0
	while i < n:
		s -= a[i - 1]
		r = a[i] * (n - i) - s
		x += a[i - 1]
		if x >= r:
			return i
		i += 1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(fun(n, a))


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li.sort(reverse=True)
	req = 0
	for i in li:
		req += li[0] - i
	if req == 0:
		print(0)
	else:
		avail = 0
		for i in range(1, n):
			req -= (n - i) * (li[i - 1] - li[i])
			avail += li[i - 1]
			if req <= avail:
				print(i)
				break


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if a[0] == a[n - 1]:
		return 0
	presum = [a[0]]
	for i in range(1, n):
		presum.append(a[i] + presum[i - 1])
	c = 0
	dons = 0
	while True:
		c += 1
		dons += a.pop()
		presum.pop()
		if dons >= a[-1] * len(presum) - presum[-1]:
			return c
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

def solve():
	for i in range(int(input())):
		n = int(input())
		lst = list(map(int, input().split()))
		sm = sum(lst)
		lst.sort()
		if lst[n - 1] == lst[0]:
			print(0)
		else:
			curr = 0
			ans = n
			for i in range(n):
				curr += lst[i]
				x = sm - curr
				if x >= lst[i] * (i + 1) - curr:
					ans = min(ans, n - i - 1)
			print(ans)
solve()


T = int(input())
for t in range(T):
	n = int(input())
	arr = [int(_) for _ in input().split()]
	arr.sort(reverse=True)
	prefix = [arr[0]]
	for i in range(1, n):
		prefix.append(prefix[i - 1] + arr[i])
	suffix = [0 for i in range(n)]
	suffix[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		suffix[i] = suffix[i + 1] + arr[i]
	reqd = arr[0] * n
	avail = prefix[-1]
	if avail >= reqd:
		print(0)
		continue
	for i in range(1, n):
		reqd = arr[i] * (n - i) - suffix[i]
		avail = prefix[i - 1]
		if avail >= reqd:
			print(i)
			break


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	(sum_, b, bsum) = (0, [0] * n, [0] * n)
	bsum[-1] = a[-1]
	for i in range(n):
		sum_ += a[i]
		b[i] = (i + 1) * a[i] - sum_
	for i in range(n - 2, -1, -1):
		bsum[i] = bsum[i + 1] + a[i]
	(count, sum_) = (0, 0)
	for i in range(n - 1, -1, -1):
		if sum_ >= b[i]:
			print(count)
			break
		count += 1
		sum_ += a[i]


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	n = int(input())
	a = sorted(map(int, input().split()))
	pre = [0] * n
	for i in range(1, n):
		pre[i] = pre[i - 1] + a[i - 1]
	sm = 0
	for i in range(n - 1, -1, -1):
		if i * a[i] <= sm + pre[i]:
			return n - 1 - i
		sm += a[i]
	return n
for _ in range(int(input())):
	print(solve())


a = int(input())
for i in range(a):
	c = int(input())
	b = list(map(int, input().split()))
	b.sort()
	b.reverse()
	if len(set(b)) == 1:
		print('0')
	else:
		j = sum(b)
		k = len(b)
		l = 0
		for i in range(len(b)):
			j -= b[i]
			k -= 1
			l += b[i]
			if b[i + 1] * k - j <= l:
				print(len(b) - k)
				break