There are $n$ boxes with different quantities of candies in each of them. The $i$-th box has $a_i$ candies inside.

You also have $n$ friends that you want to give the candies to, so you decided to give each friend a box of candies. But, you don't want any friends to get upset so you decided to eat some (possibly none) candies from each box so that all boxes have the same quantity of candies in them. Note that you may eat a different number of candies from different boxes and you cannot add candies to any of the boxes.

What's the minimum total number of candies you have to eat to satisfy the requirements?


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 50$) — the number of boxes you have.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^7$) — the quantity of candies in each box.


-----Output-----

For each test case, print a single integer denoting the minimum number of candies you have to eat to satisfy the requirements.


-----Examples-----

Input
5
5
1 2 3 4 5
6
1000 1000 5 1000 1000 1000
10
1 2 3 5 1 2 7 9 13 5
3
8 8 8
1
10000000
Output
10
4975
38
0
0


-----Note-----

For the first test case, you can eat $1$ candy from the second box, $2$ candies from the third box, $3$ candies from the fourth box and $4$ candies from the fifth box. Now the boxes have $[1, 1, 1, 1, 1]$ candies in them and you ate $0 + 1 + 2 + 3 + 4 = 10$ candies in total so the answer is $10$.

For the second test case, the best answer is obtained by making all boxes contain $5$ candies in them, thus eating $995 + 995 + 0 + 995 + 995 + 995 = 4975$ candies in total.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Mathematics

Greedy algorithms


Solutions:
def solve() -> int:
	n = int(input())
	boxes = list(map(int, input().split()))
	minimum = min(boxes)
	return sum(boxes) - n * minimum
results = []
for _ in range(int(input())):
	results.append(str(solve()))
print('\n'.join(results))


t = int(input())
for _ in range(t):
	n = int(input())
	candies = list(map(int, input().split()))
	min_candy = min(candies)
	print(sum((candy - min_candy for candy in candies)))


t = int(input())
answers = []
for i in range(t):
	su = 0
	n = int(input())
	ns = [int(k) for k in input().split()]
	m = min(ns)
	for l in ns:
		if l != m:
			su += l - m
	answers.append(su)
for j in range(t):
	print(answers[j])


import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	l = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	x = min(arr)
	for i in arr:
		ans += i - x
	print(ans)


import sys
from math import sqrt
input = sys.stdin.readline
OUTPUT = []

def print(x='', end='\n'):
	OUTPUT.append(str(x) + end)
readInt = lambda : int(input())
readIntTuple = lambda : tuple(map(int, input().split()))
readIntList = lambda : list(map(int, input().split()))
readIntSet = lambda : set(map(int, input().split()))
mapInts = lambda : map(int, input().split())

def main():
	t = readInt()
	for _ in range(t):
		n = readInt()
		candies = readIntTuple()
		lo = min(candies)
		ret = 0
		for c in candies:
			ret += c - lo
		print(ret)
try:
	main()
	sys.stdout.write(''.join(OUTPUT))
except:
	sys.stdout.write(''.join(OUTPUT))
	raise


for _ in range(int(input())):
	n = int(input())
	eat = 0
	candy = list(map(int, input().split()))
	candy.sort()
	for can in candy:
		eat = eat + (can - candy[0])
	print(eat)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	x = min(arr)
	c = 0
	for i in arr:
		c = c + (i - x)
	print(c)


for sravan in range(int(input())):
	lux = int(input())
	f = list(map(int, input().split()))
	sum_ = sum(f)
	must = min(f)
	print(sum_ - must * lux)


for _ in range(int(input())):
	len = int(input())
	l = list(map(int, input().split()))
	sum_ = sum(l)
	min_ = min(l)
	print(sum_ - min_ * len)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n * min(a) == sum(a):
		print(0)
	else:
		print(sum(a) - n * min(a))


a = int(input())
summa = []
for _ in range(a):
	cor = []
	n = int(input())
	cor = input().split()
	for j in range(n):
		cor[j] = int(cor[j])
	m = min(cor)
	summ = 0
	for i in range(n):
		summ += cor[i] - m
	summa.append(summ)
print(*summa, sep='\n')


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	print(sum(ls) - min(ls) * n)


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	input()
	inp += [input()]
for s in inp:
	arr = [int(n) for n in s.split()]
	print(sum(arr) - len(arr) * min(arr))


for h in [*open(0)][2::2]:
	b = (*map(int, h.split()),)
	print(sum(b) - min(b) * len(b))


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	m = min(li)
	ans = sum(li) - m * n
	print(ans)


def main():

	def solve(n, a):
		m = min(a)
		s = sum([x - m for x in a])
		return s
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		a = [int(x) for x in input().split()]
		ans.append(solve(n, a))
	print('\n'.join(map(str, ans)))
import sys, threading
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print(sum(a) - min(a) * len(a))


from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
from functools import lru_cache
import sys
DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
MOD = 10 ** 9 + 7
input = sys.stdin.readline
t = int(input())

def solve():
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	m = min(a)
	ans = 0
	for x in a:
		ans += x - m
	print(ans)
while t:
	solve()
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	(low, res) = (min(a), 0)
	for j in range(n):
		res += a[j] - low
	print(res)


from sys import stdin, stdout
import collections
import math

def solve():
	return

def main():
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		m = min(l)
		ans = sum([i - m for i in l])
		print(ans)
	return
input = stdin.readline
main()


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mn = min(arr)
	print(sum((x - mn for x in arr)))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	ans = [i - m for i in a]
	print(sum(ans))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	can = list(map(int, input().split()))
	mini = min(can)
	eaten = 0
	for c in can:
		if c > mini:
			eaten += c - mini
	print(eaten)


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	minn = min(arr)
	total = 0
	for i in arr:
		total += i - minn
	print(total)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	x = min(a)
	print(sum((i - x for i in a)))


for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	c = 0
	X = min(A)
	for i in A:
		c += i - X
	print(c)


for t in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	x = min(A)
	y = sum(A)
	ans = y - n * x
	print(ans)


import math
import itertools
import heapq
from math import floor, ceil

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def isSubsequence(s, t):
	for i in range(0, len(s)):
		try:
			index = t.index(s[i])
		except ValueError:
			return False
		t = t[index + 1:]
	return True
for _ in range(int(input())):
	N = input()
	arr = list(map(int, input().split()))
	a = min(arr)
	s = 0
	for i in range(len(arr)):
		s += arr[i] - a
	print(s)


t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = min(a)
	f = sum(a)
	print(f - d * n)


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = min(a)
	s = sum(a)
	print(s - m * n)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	q = min(a)
	ans = 0
	for i in a:
		ans += i - q
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	mn = min(l)
	su = 0
	for i in range(n):
		su += l[i] - mn
	print(su)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = min(arr)
	toal = m * n
	print(sum(arr) - toal)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	lst = list(map(int, input().split()))
	ans = sum(lst) - min(lst) * n
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = min(a)
	s = 0
	for j in a:
		s += j - x
	print(s, end='\n')


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	m = min(a)
	print(sum(a) - m * n)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


n = int(input())
for _ in range(n):
	k = input()
	li = list(map(int, input().split(' ')))
	mn = min(li)
	ans = 0
	for i in li:
		ans += abs(mn - i)
	print(ans)


T = int(input())
for _ in range(T):
	c = int(input())
	candies = [int(x) for x in input().strip().split(' ')]
	box = min(candies)
	print(sum([candy - box for candy in candies]))


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	print(sum(l) - N * min(l))


import math as m
import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	m = min(lis)
	s = m * a
	print(sum(lis) - s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	smallest = min(a)
	print(sum(a) - smallest * n)


import sys

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

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

def main():
	for _ in range(int(input())):
		n = int(input())
		ls = get_ls()
		ans = 0
		mn = min(ls)
		for i in ls:
			ans += i - mn
		print(ans)
main()


def function():
	m = int(input())
	count = 0
	arr = list(map(int, input().split()))
	arr.sort()
	min = arr[0]
	for ele in arr:
		if ele != min:
			count += ele - min
	print(count)
n = int(input())
for i in range(n):
	function()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	total = 0
	for j in a:
		total += j - a[0]
	print(total)


n = int(input())
b = [0] * n
for i in range(0, n):
	boxes = int(input())
	a = [int(x) for x in input().split()]
	min = a[0]
	for j in range(0, boxes):
		if a[j] < min:
			min = a[j]
	for k in range(0, boxes):
		b[i] = b[i] + a[k] - min
for l in range(0, n):
	print(b[l])


for i in range(int(input())):
	n = int(input())
	L = [int(el) for el in input().split()]
	print(sum(L) - min(L) * n)


t = int(input())
for _ in range(t):
	nnnn = int(input())
	aaa = list(map(int, input().split()))
	ddd = sum(aaa) - nnnn * min(aaa)
	print(ddd)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mini = min(a)
	count = 0
	for val in a:
		count += val - mini
	print(count)


def solve(arr):
	mn = min(arr)
	res = 0
	for i in range(len(arr)):
		res += arr[i] - mn
	return res
inpt = int(input())
for x in range(inpt):
	n = input()
	arr = [int(x) for x in input().split(' ')]
	print(solve(arr))


t = int(input())
for i in range(t):
	o = 0
	n = int(input())
	a = [0] * n
	a = list(map(int, input().split()))
	c = min(a)
	for j in range(n):
		o += a[j] - c
	print(o)


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))
tests = inp()
for i in range(tests):
	n = inp()
	d = inlt()
	minn = min(d)
	summ = 0
	for i in range(n):
		summ += d[i] - minn
	print(summ)


x = int(input())
for i in range(x):
	a = int(input())
	b = list(map(int, input().split()))
	u = sum(b)
	k = min(b)
	l = u - a * k
	print(l)


for _ in range(int(input())):
	num = int(input())
	nums = list(map(int, input().split()))
	mini = min(nums)
	snums = set(nums)
	candies = 0
	if len(snums) == 1:
		print(0)
	else:
		for e in nums:
			candies += e - mini
		print(candies)


t = int(input())
for i in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	first = nums[0]
	ans = 0
	for i in nums:
		ans += i - first
	print(ans)


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	l = input('').split()
	l = [int(x) for x in l]
	m = min(l)
	count = 0
	for i in l:
		count = count + (i - m)
	print(count)


num = int(input())
for i in range(num):
	input()
	num = list(map(int, input().split()))
	st1 = 0
	min = 100000000000
	for m in num:
		if m < min:
			min = m
	for j in num:
		st1 += j - min
	print(st1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = sum(a) - n * min(a)
	print(ans)


for n in range(int(input())):
	input()
	a = [*map(int, input().split())]
	print(-min(a) * len(a) + sum(a))


testcase = int(input())
arr = []
for _ in range(testcase):
	numBox = int(input())
	arrBox = list(map(int, input().split()))
	arr.append(arrBox)
for i in arr:
	print(sum(i) - len(i) * min(i))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()[:n]))
	m = min(arr)
	ans = 0
	for item in arr:
		ans += item - m
	print(ans)


m = int(input())
for i in range(m):
	n = int(input())
	list1 = [int(x) for x in input().split()]
	a = min(list1)
	result = 0
	if n > 1:
		for i in list1:
			b = i - a
			result += b
		print(result)
	else:
		print('0')


t = int(input())
for te in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mm = min(arr)
	ans = 0
	for i in arr:
		ans += i - mm
	print(ans)


for _ in range(int(input())):
	f = int(input())
	arr = list(map(int, input().split()))
	diff = sum(arr) - f * min(arr)
	print(diff)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(j) for j in input().split()]
	l.sort()
	k = 0
	for j in range(1, n):
		k = k + l[j] - l[0]
	print(k)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = min(l)
	d = 0
	for i in range(len(l)):
		d = d + abs(l[i] - c)
	print(d)


a = int(input())
while a:
	x = int(input())
	y = [int(i) for i in input().split()]
	k = sum(y) - min(y) * x
	print(k)
	a -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	num = list(map(int, input().split()))
	if len(num) == 1:
		print(0)
		continue
	minimum = min(num)
	output = 0
	for i in num:
		output += i - minimum
	print(output)


for _ in range(int(input())):
	input()
	nums = list(map(int, input().split()))
	minimum = min(nums)
	print(sum([n - minimum for n in nums]))


for i in range(int(input())):
	len = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	minl = min(l)
	print(s - minl * len)


t = int(input())
for i in range(t):
	num = int(input())
	arr = list(map(int, input().split(' ')))
	candies = 0
	minimum = min(arr)
	for ind in range(num):
		if arr[ind] != minimum:
			candies = candies + (arr[ind] - minimum)
		else:
			pass
	print(candies)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = sum(l) - min(l) * n
	print(ans)


for iq in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	m = min(ls)
	cnt = 0
	for i in range(n):
		cnt += ls[i] - m
	print(cnt)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	s1 = min(l)
	s2 = max(l)
	if s1 == s2:
		print(0)
		continue
	c = 0
	for i in l:
		c += i - s1
	print(c)


number_test = int(input())
for i in range(number_test):
	number_box = int(input())
	quantity = list(map(int, input().split()))
	answer = 0
	minimum = quantity[0]
	for i in range(1, len(quantity)):
		if quantity[i] < minimum:
			minimum = quantity[i]
	for i in quantity:
		if i != minimum:
			answer += i - minimum
	print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = min(l)
	sm = 0
	for i in l:
		i = i - m
		sm = sm + i
	print(sm)


n = int(input())
for _ in range(n):
	k = int(input())
	a = list(map(int, input().split()))
	s = 0
	b = min(a)
	for i in a:
		s += i - b
	print(s)


def min(a):
	min = a[0]
	for i in a:
		min = min if min < i else i
	return min
t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split(' ')))
	s1 = min(s)
	sum = 0
	for i in range(n):
		if s[i] > s1:
			sum += s[i] - s1
	print(sum)


def solution():
	n = int(input())
	for i in range(n):
		num_boxes = int(input())
		l = list(map(int, input().split()))
		minimum_val = min(l)
		total = sum(l)
		res = total - minimum_val * num_boxes
		print(res)
solution()


n = int(input())
A = []
T = []
for i in range(n):
	A += [int(input())]
	T += [list(map(int, input().split()))]
for item in T:
	print(sum(item) - min(item) * len(item))


def ii():
	return int(input())

def il(sep=' '):
	if sep == '':
		return [int(i) for i in input()]
	return [int(i) for i in input().split(sep)]
t = ii()
for tt in range(t):
	n = ii()
	a = il()
	if n == 1:
		print(0)
		continue
	x = min(a)
	ans = 0
	for i in a:
		ans += i - x
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	mn = min(l)
	cnt = 0
	for i in l:
		cnt += i - mn
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	hey = len(l)
	k = min(l)
	meet = sum(l) - hey * k
	print(meet)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mi = min(l)
	sum = 0
	for i in l:
		sum += i - mi
	print(sum)


t = int(input())
for i in range(t):
	n = int(input())
	boxes = list(map(int, input().split()))
	m = min(boxes)
	count = 0
	for j in range(n):
		count += boxes[j] - m
	print(count)


a = int(input())
arr = []
for i in range(a):
	x = int(input())
	Num = list(map(int, input().split()))
	Min = min(Num)
	Diff = sum(Num) - int(Min) * x
	arr.append(Diff)
for i in range(a):
	print(arr[i])


t = int(input())
for i in range(t):
	num = int(input())
	n = [int(x) for x in input().split()]
	n.sort()
	sum = 0
	for j in range(1, len(n)):
		sum = sum + n[j] - n[0]
	print(sum)


for _ in range(int(input())):
	m = int(input())
	a = list(map(int, input().split()))
	f = sum(a) - m * min(a)
	print(f)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	minn = min(a)
	for i in a:
		l.append(i - minn)
	print(sum(l))


from math import *
import os

def codebyShamsov_saf(n):
	if n > 0:
		return False
	return True
a = int(input())
for __________________ in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	s = 0
	q = min(c)
	for i in c:
		s += i - q
	print(s)


t = int(input())
for cases in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mini = min(arr)
	summ = 0
	for i in range(n):
		summ += arr[i] - mini
	print(summ)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	r = l[0]
	s = 0
	if l[0] == l[n - 1]:
		print('0')
	else:
		for k in range(1, n):
			s = s + (l[k] - r)
		print(s)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	total = 0
	arr.sort()
	for i in range(1, n):
		total += arr[i] - arr[0]
	return total
t = int(input())
for i in range(t):
	print(main())


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	minn = min(arr)
	ans = sum(arr) - n * minn
	print(ans)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	candies = input().split()
	x = list(map(int, candies))
	x.sort()
	print(sum(x) - x[0] * n)
	t = t - 1