Polycarp got an array of integers $a[1 \dots n]$ as a gift. Now he wants to perform a certain number of operations (possibly zero) so that all elements of the array become the same (that is, to become $a_1=a_2=\dots=a_n$).

In one operation, he can take some indices in the array and increase the elements of the array at those indices by $1$.

For example, let $a=[4,2,1,6,2]$. He can perform the following operation: select indices 1, 2, and 4 and increase elements of the array in those indices by $1$. As a result, in one operation, he can get a new state of the array $a=[5,3,1,7,2]$.

What is the minimum number of operations it can take so that all elements of the array become equal to each other (that is, to become $a_1=a_2=\dots=a_n$)?


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$)  — the number of test cases in the test.

The following are descriptions of the input test cases.

The first line of the description of each test case contains one integer $n$ ($1 \le n \le 50$)  — the array $a$.

The second line of the description of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)  — elements of the array $a$.


-----Output-----

For each test case, print one integer  — the minimum number of operations to make all elements of the array $a$ equal.


-----Examples-----

Input
3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11
Output
3
4
1


-----Note-----

First test case:

$a=[3,4,2,4,1,2]$ take $a_3, a_5$ and perform an operation plus one on them, as a result we get $a=[3,4,3,4,2,2]$.

$a=[3,4,3,4,2,2]$ we take $a_1, a_5, a_6$ and perform an operation on them plus one, as a result we get $a=[4,4,3,4,3,3]$.

$a=[4,4,3,4,3,3]$ we take $a_3, a_5, a_6$ and perform an operation on them plus one, as a result we get $a=[4,4,4,4,4,4]$.

There are other sequences of $3$ operations, after the application of which all elements become equal.

Second test case:

$a=[1000,1002,998]$ 2 times we take $a_1, a_3$ and perform an operation plus one on them, as a result we get $a=[1002,1002,1000]$.

$a=[1002,1002,1000]$ also take $a_3$ 2 times and perform an operation plus one on it, as a result we get $a=[1002,1002,1002]$.

Third test case:

$a=[12,11]$ take $a_2$ and perform an operation plus one on it, as a result we get $a=[12,12]$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics


Solutions:
from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input().strip())):
	n = inp_int()
	a = inp_lis()
	x = max(a)
	y = min(a)
	print(x - y)


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


from sys import stdin

def solve():
	for _ in range(int(stdin.readline().strip())):
		n = int(stdin.readline().rstrip())
		A = list(map(int, stdin.readline().rstrip().split()))
		print(max(A) - min(A))
solve()


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	print(max(a) - min(a))


import functools
import sys
import typing
from typing import Callable, Dict, List, Set, Tuple
sys.setrecursionlimit(10 ** 6)
sinput: Callable[..., str] = sys.stdin.readline
debug = functools.partial(print, file=sys.stderr)
MOD: int = 998244353
INF: float = float('Inf')
IINF: int = sys.maxsize // 2

def main() -> None:
	_ = int(sinput())
	a = list(map(int, sinput().split()))
	print(max(a) - min(a))
t = int(sinput())
for _ in range(t):
	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()
	print(max(arr) - min(arr))


n = int(input())
lst = []
for q in range(n):
	m = int(input())
	a = list(map(int, input().split()))
	lst.append(max(a) - min(a))
for p in range(len(lst)):
	print(lst[p])


import sys
input = sys.stdin.readline

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

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	n = inp()
	for _ in range(n):
		SIZE = inp()
		arr = inlt()
		result = max(arr) - min(arr)
		print(result)
	return 0
main()


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()))
	total = 0
	print(max(arr) - min(arr))


import sys

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

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		get_print_int(max(arr) - min(arr))
solve()


import sys, os
if os.path.exists('input'):
	sys.stdin = open('input', 'r')
input = sys.stdin.readline

def solve():
	input()
	a = list(map(int, input().split()))
	mi = min(a)
	ma = max(a)
	return ma - mi
t = int(input())
for _ in range(t):
	print(solve())


for i in [*open(0)][2::2]:
	i = list(map(int, i.split()))
	m = max(i)
	l = min(i)
	print(m - l)


r = int(input())
res = []
for i in range(r):
	input()
	arr = list(map(int, input().split()))
	res.append(max(arr) - min(arr))
for i in res:
	print(i)


k = []
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k.append(max(l) - min(l))
for items in k:
	print(items)


from math import *
import sys
input = sys.stdin.readline

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

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def rSort(arr1, arr2):
	(arr1, arr2) = [list(tuple) for tuple in zip(*sorted(arr1, arr2))]
	return (arr1, arr2)

class Solution:

	def _init_(self):
		self.ans = 0

	def solve(self, arr):
		return max(arr) - min(arr)
sol = Solution()
t = int(input())
for i in range(t):
	n = input()
	arr = list(invr())
	print(sol.solve(arr))


t = int(input())
result = []
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	result.append(max(s) - min(s))
for i in range(t):
	print(result[i])


import sys
input = lambda : sys.stdin.readline().strip()

def solve():
	input()
	arr = list(map(int, input().split()))
	return max(arr) - min(arr)
for _ in range(int(input())):
	print(solve())


from sys import stdin, stdout

def A():
	num_test = int(stdin.readline())
	for n in range(num_test):
		array_size = int(stdin.readline())
		a = list(map(int, stdin.readline().split()))
		print(int(max(a) - min(a)))
A()


n = int(input())
l1 = []
for i in range(n):
	num = int(input())
	l = list(map(int, input().split()))
	l1.append(max(l) - min(l))
for i in l1:
	print(i)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	print(max(li) - min(li))


t = int(input())
ans = []
while t != 0:
	t -= 1
	n = int(input())
	li = list(map(int, input().split()))
	(a, b) = (max(li), min(li))
	ans.append(a - b)
for i in ans:
	print(i)


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


from cmath import inf
from math import inf

def main():

	def solve(n, a):
		mn = inf
		mx = -inf
		for x in a:
			if x > mx:
				mx = x
			if x < mn:
				mn = x
		return mx - mn
	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()


def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	return max(a) - min(a)
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


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


n = int(input())
q = []
for z in range(n):
	t = int(input())
	m = input()
	l = [int(i) for i in m.split()]
	mx = max(l)
	mn = min(l)
	q.append(mx - mn)
for i in q:
	print(i)


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


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


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


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


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	d = sorted([*map(int, input().split())])
	print(d[-1] - d[0])


def solve(a):
	return max(a) - min(a)
test = int(input())
for t in range(0, test):
	n = input()
	a = list(map(int, input().split()))
	print(solve(a))


c = []
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c.append(l)
for i in c:
	print(max(i) - min(i))


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


from sys import stdin
t = stdin.readline()
for _ in range(int(t)):
	n = stdin.readline()
	arr = stdin.readline().strip().split(' ')
	arr = list(map(lambda a: int(a), arr))
	print(max(arr) - min(arr))


import sys
input = sys.stdin.readline
t = int(input())
for t in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	n1 = -1
	n2 = 10 ** 10
	for num in a:
		if num > n1:
			n1 = num
		if num < n2:
			n2 = num
	print(n1 - n2)


def ent(l):
	l1 = list()
	for i in l:
		l1.append(int(i))
	return l1
x = int(input())
l1 = list()
l2 = list()
for i in range(x):
	a = int(input())
	ch = input()
	l = ch.split(' ')
	l1 = ent(l)
	l2.append(max(l1) - min(l1))
for j in l2:
	print(j)


a = int(input())
arr = []
for i in range(a):
	b = int(input())
	c = [int(g) for g in str(input()).split()]
	c.sort()
	arr.append(c[-1] - c[0])
for i in arr:
	print(i)


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


t = int(input())
l = []
for i in range(0, t):
	n = int(input())
	m = [int(x) for x in input().split()]
	l.append(m)
for j in range(0, t):
	print(max(l[j]) - min(l[j]))


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


t = int(input())
s = []
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split(' ')]
	l.sort()
	a = l[-1] - l[0]
	s.append(a)
for i in s:
	print(i)


import sys
input = sys.stdin.readline
output = sys.stdout.write

def main():
	tests = int(input().rstrip())
	for i in range(tests):
		length_ = int(input().rstrip())
		if length_ == 1:
			output('0')
			output('\n')
			input()
		else:
			list_ = list(map(int, input().rstrip().split()))
			list_.sort()
			dif = list_[-1] - list_[0]
			output(str(dif))
			output('\n')
main()


import sys

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

def get_string():
	return sys.stdin.readline().strip()
FILE = False
if FILE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = get_int()
for i in range(t):
	s = get_int()
	s = get_string()
	s_list = s.split()
	map_object = map(int, s_list)
	array = list(map_object)
	top = max(array)
	bottom = min(array)
	answer = top - bottom
	sys.stdout.write(str(answer))
	sys.stdout.write('\n')


import collections
arraynum = int(input())
arrays = []
for i in range(arraynum):
	numnumbers = int(input())
	array = list(map(int, input().split()))
	arrays.append(array)
for arr in arrays:
	print(max(arr) - min(arr))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(max(a) - min(a))


def plusone(array):
	result = []
	value = 0
	for i in array:
		mini = min(i)
		maxi = max(i)
		value = maxi - mini
		result.append(value)
	return result
arr = []
NoofTestcase = int(input())
for i in range(NoofTestcase):
	NoofElement = int(input())
	temp = list(map(int, input().split()))[:NoofElement]
	arr.append(temp)
res = plusone(arr)
for i in res:
	print(i)


t = int(input())
f = []
for i in range(t):
	(l, n) = ([], 0)
	n = int(input())
	l = [int(i) for i in input().split()]
	mx = max(l)
	mi = min(l)
	f.append(mx - mi)
for i in f:
	print(i)


Q = int(input())
W = []
for i in range(Q):
	n = int(input())
	W.append(list(map(int, input().split())))
for i in range(Q):
	print(max(W[i]) - min(W[i]))


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


def int_list_input():
	a = list(map(int, input().split()))
	return a

def solve():
	n = int(input())
	arr = int_list_input()
	print(max(arr) - min(arr))
for _ in range(int(input())):
	solve()


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


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


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


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(abs(max(l) - min(l)))


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


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


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


for _ in range(int(input())):
	test_length = input()
	test = list(map(int, input().split()))
	print(max(test) - min(test))


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


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


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


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


t = int(input())
for zz in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	z = max(l)
	c = 0
	print(max(l) - min(l))