Chef has an array A having N elements. Chef wants to make all the elements of the array equal by repeating the following move.

Choose any integer K between 1 and N (inclusive). Then choose K distinct indices i_{1} , i_{2}, \dots, i_{K}, and increase the values of A_{i_{1}} , A_{i_{2}} , \dots , A_{i_{K}} by 1.

Find the minimum number of moves required to make all the elements of the array equal. 

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

- The first line contains T denoting the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N denoting the number of elements in A.
- The second line of each test case contains N space separated integers A_{1}, A_{2}, \dots, A_{N}.

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

For each test case, print a single line containing one integer denoting the minimum number of moves required to make all the elements of the array equal. 

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
- The sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
2
3
1 3 1
3
2 2 2
----- Sample Output 1 ------ 
2
0
----- explanation 1 ------ 
- Test Case $1$: In the first move, Chef can choose $K = 2$, and choose the indices $\{1 , 3\}$. After increasing $A_{1}$ and $A_{3}$ by $1$, the array will become $[2 , 3 , 2]$.
In the second move, Chef can choose $K = 2$, and choose the indices $\{1 , 3\}$. After increasing $A_{1}$ and $A_{3}$ by $1$, the array will become $[3 , 3 , 3]$, and hence all the elements become equal. 

- Test Case $2$: All the elements of the array are equal, hence no move is required.

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(max(a) - min(a))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	min1 = min(l)
	max1 = max(l)
	print(max1 - min1)


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	x1 = max(x)
	x2 = min(x)
	s = x1 - x2
	print(s)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))[:N]
	print(max(A) - min(A))


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


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


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if set(a) == {a[0]}:
		print('0')
	else:
		print(max(a) - min(a))


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	a = max(l1)
	b = min(l1)
	print(a - b)


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


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


t = int(input())
for j in range(t):
	n = int(input())
	l = list(map(int, input(' ').split(' ')))
	print(max(l) - min(l))


t = int(input())
for T in range(t):
	n = int(input())
	narr = list(map(int, input().split()))
	minarr = 100000
	maxarr = 0
	for i in range(n):
		if narr[i] > maxarr:
			maxarr = narr[i]
		if narr[i] < minarr:
			minarr = narr[i]
	print(maxarr - minarr)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	maxi = a[0]
	steps = 0
	i = 0
	if a[0] == a[-1]:
		print(steps)
	else:
		while i < n - 1:
			i += 1
			steps += a[0] - (a[i] + steps)
		print(steps)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	maxi = max(a)
	mini = min(a)
	print(maxi - mini)


T = int(input())
while T > 0:
	N = int(input())
	arr = list(map(int, input().split()))
	print(max(arr) - min(arr))
	T -= 1


for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	print(max(l) - min(l))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if len(s) == 1:
		print(0)
	else:
		l = list(s)
		print(max(l) - min(l))


t = int(input())
for i in range(t):
	n = int(input())
	array = list((int(item) for item in input().split()))
	print(max(array) - min(array))


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	print(max(l) - min(l))


for i in '*' * int(input()):
	input()
	a = sorted([*map(int, input().split())])
	print(a[-1] - a[0])


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	k = max(arr)
	n = min(arr)
	print(k - n)
	t = t - 1


tc = int(input())
for i in range(tc):
	arsize = int(input())
	listbox = list(map(int, input().split()))
	print(max(listbox) - min(listbox))


test = int(input())
for i in range(test):
	number = int(input())
	List = list(map(int, input().split()))
	print(max(List) - min(List))


a = int(input())
for i in range(a):
	b = int(input())
	s = list(map(int, input().split()))
	print(max(s) - min(s))


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


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m1 = max(l)
	m2 = min(l)
	print(m1 - m2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a_set = list(set(a))
	a_max = max(a_set)
	a_min = min(a_set)
	steps = a_max - a_min
	print(steps)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	maxi = max(ar)
	ma = -10000000
	for j in range(n):
		ma = max(ma, maxi - ar[j])
	print(ma)


for i in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	array = sorted(array)
	print(array[n - 1] - array[0])


a = int(input(''))
for i in range(a):
	x = int(input(''))
	v = [int(x) for x in input('').split()]
	k = list(v)
	print(max(k) - min(k))


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


def big(n):
	big = 0
	for i in range(len(n)):
		if n[i] > big:
			big = n[i]
	return big

def s_op(a):
	small = a[0]
	for i in range(len(a)):
		if a[i] < small:
			small = a[i]
	return small

def main():
	langth = int(input())
	one = [int(x) for x in input().split()]
	print(big(one) - s_op(one))
for t in range(int(input())):
	main()


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	max1 = list1[0]
	min1 = list1[0]
	for s in list1:
		if s > max1:
			max1 = s
		if s < min1:
			min1 = s
	print(max1 - min1)


t = int(input())
if 1 <= t <= 10 ** 4:
	for i in range(t):
		n = int(input())
		if 1 <= n <= 10 ** 5:
			a = list(map(int, input().split()))
			v = 0
			for j in a:
				if 1 <= j <= 10 ** 5:
					v += 1
			if n == v:
				print(max(a) - min(a))


def result(n, a):
	mn = min(a)
	mx = max(a)
	return mx - mn
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	r = result(n, a)
	print(r)


t = int(input())
while t:
	t -= 1
	n = int(input())
	lst = list(map(int, input().split()))
	print(max(lst) - min(lst))