It's John's birthday; he has brought some candies in distribute among N of his friends. Being a good friend, he decided to distribute all of his candies equally among his friend and he don't want to keep any for himself. He left the task of distributing candies up to his friends, but his friends haven't done a great job in distributing them and now they all have unequal amount of candies.
He asked all of his friends to keep all the candies in their hands (A[1] to A[N]) so that he can redistribute the candies. Taking a candy away from someone makes them sad and makes the person who gets it happy. Thus, you do not want to do many operations on the number of candies.
Here each operation stands for, taking away 1 candy from someone and giving it to somebody else.
After applying the operations, he might not be able to distribute all the candies among all of your friends, and you might need to buy some more candies as well. Buying each candy will be counted as 1 operation as well. John is saving up for his birthday party in the evening and so he wants to spend the least amount of money on candies as possible.
Thus, he asks for your help. You have to find the minimum number of operations required to make the distributions equal.

-----Input:-----
- The first line consists of the number T representing the number of test cases.
- Each test case consists of 2 lines.
- The first line contains of the number N representing the number of friends.
- The second line contains space separated numbers (A[1] to A[N]) representing the number of candies each friend currently has.

-----Output:-----
For each test case, you much print the minimum number of operations.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $0 \leq A[i] \leq 10^9$

-----Sample Input:-----
3

4

7 8 6 4

6

7 3 10 2 3 8

1

10   

-----Sample Output:-----
4

10

0

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import math
for t in  range(int(input())):
    n=int(input())
    a=[int(i) for i in input().split()]
    div=sum(a)/n
    div=math.ceil(div)
    count=div*n-sum(a)
    for i in a:
        if i>div:
            count+=i-div
    print(count)

# cook your dish here
import math
t  =int(input())
for i in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    m = math.ceil(sum(l)/n)
    ans=0
    for i in l:
        x = m-i
        if x>0 :
            ans=ans + x
    print(ans)


for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=sum(l)
    q=s//n
    r=s%n
    if(r!=0):
        q+=1
    extra=0
    k=[]
    le=0
    ans=0
    for i in l:
        if(i>q):
            extra+=i-q
        elif i<q:
            ans+=q-i
    print(ans)

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=sum(l)
    q=s//n
    r=s%n
    if(r!=0):
        q+=1
    extra=0
    k=[]
    le=0
    ans=0
    for i in l:
        if(i>q):
            extra+=i-q
        elif i<q:
            ans+=q-i
    print(ans)

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=sum(l)
    q=s//n
    r=s%n
    if(r!=0):
        q+=1
    extra=0
    k=[]
    le=0
    ans=0
    for i in l:
        if(i>q):
            extra+=i-q
        elif i<q:
            ans+=q-i
    print(ans)

# cook your dish here
for testcase in range(int(input())):
    n = int(input())
    values = list(map(int, input().split()))
    
    current_total = sum(values)
    
    equality_value = current_total/n
    # lines 10-11 are ceil() function equivalent
    if equality_value>int(equality_value):equality_value+=1
    equality_value = int(equality_value)
    
    deviations = list()
    net_deviations = 0
    
    for value in values:
        deviation = value - equality_value
        deviations.append(deviation)
        net_deviations += deviation
        
    # print(current_total, equality_value, deviations, net_deviations)

    minimum_operations = abs(net_deviations)    # net_deviations has to be a negative value, using abs() just to be foolproof  
    
    for deviation in deviations:
        if deviation>0:minimum_operations += deviation
        
    print(minimum_operations)


t= int(input())
for i in range(t):
	n= int(input())
	a= list(map(int,input().split()))
	total= sum(a)
	if total%n!=0:
		new_total= int(n*(int(total/n)+1))
	else:
		new_total=total
	cand= new_total//n 
	op= new_total-total
	
	for j in a:
		if j>cand:
			op+= (j-cand)
	print(op)

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=sum(l)
    q=s//n
    r=s%n
    if(r!=0):
        q+=1
    extra=0
    k=[]
    le=0
    ans=0
    for i in l:
        if(i>q):
            extra+=i-q
        elif i<q:
            ans+=q-i
    print(ans)

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=sum(l)
    q=s//n
    r=s%n
    if(r!=0):
        q+=1
    extra=0
    k=[]
    le=0
    for i in l:
        if(i>q):
            extra+=i-q
        elif i<q:
            k.append(i)
            le+=1
    ans=0
    for i in range(le):
        if(extra>=(q-k[i])):
            extra-=(q-k[i])
            ans+=q-k[i]
        else:
            ans+=q-k[i]
    print(ans)



import math
t = int(input())
for i in range(t):
    n = int(input())
    lst = list(map(int,input().split()))
    v = math.ceil(sum(lst)/n)
    b = 0
    t = 0
    for i in lst:
        if i > v:
            b+=(i-v)
            
    t+=b
    
    for i in lst:
        if i < v :
            b-=(v-i)
            i+=(v-i)
            
    t+=abs(b)
    print(t)


import math
t = int(input())
for i in range(t):
    n = int(input())
    lst = list(map(int,input().split()))
    v = math.ceil(sum(lst)/n)
    b = 0
    t = 0
    for i in lst:
        if i > v:
            b+=(i-v)
            
    t+=b
    
    for i in lst:
        if i < v :
            b-=(v-i)
            i+=(v-i)
            
    t+=abs(b)
    print(t)


# cook your dish here
for _ in range(int(input())):
     n=int(input())
     a=list(map(int,input().split()))
     candies=sum(a)
     ans=0
     r=candies%n
     d=candies//n
     if(r==0):
          ans=0
     else:
          d=d+1
          ans=(n*d)-candies
     for i in a:
          if(i>d):
               ans+=i-d
     print(ans)
               
                    


# cook your dish here
import math
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    x=sum(a)
    b=math.ceil(x/len(a))
    op=((b*len(a))-x)
    for i in range(len(a)):
        if a[i]>=b:
            op+=(a[i]-b)
    print(op)

for _ in range(int(input())):
    n=int(input())
    a=[int(i) for i in input().split()]
    s=sum(a)/n
    m=0
    store=0
    buy=0
    if int(s)!=s:
        s=int(s)+1
    for i in a:
        if(i<s):
            buy+=s-i
        elif(i>s):
            store+=i-s
            m+=i-s
    if(store<buy):
        m+=buy-store
    print(m)


# cook your dish here
import math

t= int(eval(input("")))
while(t!=0):
        size = int(eval(input("")))
        a1 = (input("").split())
        arr= []
        allcandies=0
        for i in range(len(a1)):
                arr.append(int(a1[i]))
                allcandies+=arr[i]
        
        candies = math.ceil(allcandies/size)
        ans = 0
        extra = 0
        for i in range(len(arr)):
                if arr[i]>candies:
                        ans+=arr[i]-candies
                        extra +=arr[i]-candies
                
                if arr[i]<candies:
                        extra-= candies- arr[i]
        
        if extra<0:
                ans+=abs(extra)
        print(ans)

        t-=1


# cook your dish here
for _ in range(int(input())):
    n = int(input())
    can = list(map(int, input().split()))
    s = sum(can)
    if(s%n == 0):
        dist = s//n
        op = 0
        for i in range(n):
            if(can[i]>dist):
                op += (can[i] - dist)
        print(op)
    else:
        op = (n - (s%n))
        dist = (s//n)+1
        for i in range(n):
            if(can[i]>dist):
                op += (can[i] - dist)
        print(op)

# cook your dish here
for _ in range(int(input())):
    N=int(input())
    l=[int(i) for i in input().split()]
    sum=0
    for i in l:
        sum+=i 
    if sum%N==0:
        avg=sum//N 
    else:
        avg=sum//N+ 1 
    
    no_of_operations=avg*N-sum
    for i in l:
        if i>avg:
            no_of_operations+=i-avg
        else:
            pass
        
    print(no_of_operations)

# cook your dish here
a=int(input())
z=[]
for i in range(a):
    b=int(input())
    c=list(map(int,input().split()))
    p=0
    if sum(c)%b!=0:
        p=p+b-(sum(c)%b)
        q=int(sum(c)/b)+1
    else:
        q=int(sum(c)/b)
    
    for j in c:
        if j>q:
            p=p+j-q
    z.append(p)
for i in z:
    print(i)

try:
    t = int(input())
    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        s = sum(arr)
        count = 0
        if s%n==0:
            each = s//n
        else:
            each = (s//n)+1
        for i in range(n):
            if arr[i]<each:
                count += (each - arr[i])
        print(count)
except EOFError:
    pass