In the school computer room there are n servers which are responsible for processing several computing tasks. You know the number of scheduled tasks for each server: there are m_{i} tasks assigned to the i-th server.

In order to balance the load for each server, you want to reassign some tasks to make the difference between the most loaded server and the least loaded server as small as possible. In other words you want to minimize expression m_{a} - m_{b}, where a is the most loaded server and b is the least loaded one.

In one second you can reassign a single task. Thus in one second you can choose any pair of servers and move a single task from one server to another.

Write a program to find the minimum number of seconds needed to balance the load of servers.


-----Input-----

The first line contains positive number n (1 ≤ n ≤ 10^5) — the number of the servers. 

The second line contains the sequence of non-negative integers m_1, m_2, ..., m_{n} (0 ≤ m_{i} ≤ 2·10^4), where m_{i} is the number of tasks assigned to the i-th server.


-----Output-----

Print the minimum number of seconds required to balance the load.


-----Examples-----
Input
2
1 6

Output
2

Input
7
10 11 10 11 10 11 11

Output
0

Input
5
1 2 3 4 5

Output
3



-----Note-----

In the first example two seconds are needed. In each second, a single task from server #2 should be moved to server #1. After two seconds there should be 3 tasks on server #1 and 4 tasks on server #2.

In the second example the load is already balanced.

A possible sequence of task movements for the third example is:  move a task from server #4 to server #1 (the sequence m becomes: 2 2 3 3 5);  then move task from server #5 to server #1 (the sequence m becomes: 3 2 3 3 4);  then move task from server #5 to server #2 (the sequence m becomes: 3 3 3 3 3). 

The above sequence is one of several possible ways to balance the load of servers in three seconds.

Difficulty: interview

Starter code:

Solutions:
diff=0
x = int(input())
l = list(map(int, input().split(' ')))
s = sum(l)
k = s//x
knum = (k+1)*x-s
kpnum = x - knum
a = knum * [k] + [k+1] * kpnum
a.sort()
l.sort()
for i in range(len(a)):
    diff += abs(a[i]-l[i])
print(int(diff/2))

#!/usr/bin/env python3

def solve():
    N = int(input())
    tasks = list(map(int, input().split()))
    avg = sum(tasks)//N
    missing = [max(avg - t, 0) for t in tasks]
    remaining = [max(t - avg - 1, 0) for t in tasks]

    print(max(sum(missing), sum(remaining)))




def __starting_point():
    solve()

__starting_point()

n=int(input())
L=[int(x) for x in input().split(' ')]
L.sort()
tot=sum(L)
small=tot//n
numsmall=n-(tot-small*n)
ans=0
for i in range(0,numsmall):
    ans+=max(0,small-L[i])
for i in range(numsmall,n):
    ans+=max(0,small+1-L[i])
print(ans)


def grimper(M):
    k = 1
    while M[k]<M[k-1]:
        M[k],M[k-1] = M[k-1],M[k]
        k+=1
    k = n-1
    while M[k]<M[k-1]:
        M[k],M[k-1] = M[k-1],M[k]
        k-=1
    return M

n = int(input())
M = list(map(int, input().split()))
s = sum(M)
m = s//n
if s % n:
    c = 1
else:
    c = 0
r1 = 0
r2 = 0
for k in range(n):
    if M[k]<m:
        r1 += m - M[k]
    if M[k]>m+c:
        r2 += M[k] - (m+c)
print(max([r1,r2]))
        


n = int(input())
a = list(map(int, input().split()))
a.sort()
sum = 0
for i in range(n):
    sum += a[i]
z1 = sum // n
z2 = sum // n + 1
col = sum % n
col = n - col
ans = 0
for i in range(col):
    ans += abs(z1 - a[i])
for t in range(col, n):
    ans += abs(a[t] - z2)
print(ans // 2)


n = int(input())
l = list(map(int, input().split()))
s = sum(l)
lo = s//n
hi = s//n + 1
lo_n = -1
for i in range(len(l)+1):
    if lo*i + hi*(len(l)-i) == s:
        lo_n = i
        break
if lo_n < 0 or lo_n > len(l):
    assert(False)
hi_n = n-lo_n
l = sorted(l)
l2 = []
for i in range(lo_n):
    l2.append(lo)
for i in range(hi_n):
    l2.append(hi)
ans = 0
for i in range(len(l)):
    ans += abs(l[i]-l2[i])
print(ans//2)


n = int(input())
m = [int(x) for x in input().split()]
m.sort()
sum_m = sum(m)
mean = sum_m // n
dif = sum_m - mean * n
res = 0
for i in range(n):
    if i < n - dif:
        res += abs(m[i] - mean)
    else:
        res += abs(m[i] - mean - 1)
print(res // 2)


n=int(input())
a=[int(i) for i in input().split()]
a.sort()
Yu=sum(a)%n
pin=sum(a)//n
re=0

for i in a:
    if i<pin:
        re+=pin-i
    else:
        break

if Yu==0:
    print(re)
else:
    re_2=0
    for i in a:
        if i <=pin+1:
            continue
        else:
            re_2+=i-pin-1
    print(max(re,re_2))
            


def inpList():
    return list(map(int,input().split()))
def inp():
    return int(input())
n=inp()
a=inpList()
x=sum(a)
p=x//n
t=x%n
a.sort()
suma=0
for i in range(n-t):
    suma+=abs(p-a[i])
for i in range(n-t,n):
    suma+=abs(a[i]-p-1)
print(suma//2)


n=int(input())
l=input().split()
s=0
for i in range(n):
    l[i]=int(l[i])
    s+=l[i]
if(s%n==0):
    q=s//n
    r=0
    for i in range(n):
        if(l[i]>q):
            r+=l[i]-q
    print(r)
else:
    p=s%n
    q=(s-s%n)//n
    r=0
    l.sort()
    l.reverse()
    for i in range(n):
        if(i<p):
            if(l[i]>q+1):
                r+=l[i]-q-1
        else:
            if(l[i]>q):
                r+=l[i]-q
    print(r)

n=int(input())
a=list(map(int,input().split()))
s=0
a.sort(reverse=True)
for i in range (n):
    s+=a[i]
cel=int(s/n)
ost=s%n
i=0
kol=0
while a[i]>cel:
    if ost!=0:
        kol+=a[i]-cel-1
        ost-=1
    else:
        kol+=a[i]-cel
    i+=1
print(kol)


n, m = int(input()), list(map(int, input().split()))
a, b = sum(m) // n, (sum(m) + n - 1) // n
print(max(sum(a - x for x in m if x < a), sum(x - b for x in m if x > b)))


#!/usr/bin/env python3

n = int(input())
arr = list(map(int, input().split()))
assert len(arr) == n

total = sum(arr)
avg1 = total // n
avg2 = avg1 + (0 if total % n == 0 else 1)

seconds = 0
offset = 0
for n in arr:
    if n < avg1:
        seconds += (avg1 - n)
        offset += (avg1 - n)
    elif n > avg2:
        seconds += (n - avg2)
        offset += (avg2 - n)

seconds = (seconds + abs(offset)) // 2
print(seconds)


import math

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
total = sum(lst)
more = total - math.floor(total / n) * n
result = [ math.floor(total / n) for i in range(n) ]
for i in range(n - more, n):
    result[i] += 1
sum_move = 0
for (ori, res) in zip(lst, result):
    if ori > res:
        sum_move = sum_move + (ori - res)
print(sum_move)


import math

def average(args):
	sum = 0
	count = 0
	for arg in args:
		sum += arg
		count += 1
	if count > 0:
		sum = sum / count
	return sum

n = int(input())
args = [int(x) for x in input().split()]

avg = average(args)

up = 0
down = 0
for arg in args:
	if arg > avg:
		down += arg - math.ceil(avg)
	elif arg < avg:
		up += math.floor(avg) - arg

print(max(up, down))

n = int(input())
m = list(map(int,input().split()))
ss = sum(m)
dd = ss // n
maxdd = ss % n
mindd = n-maxdd
ans = 0
for a in m:
	if a>=dd and maxdd == 0:
		ans += a-dd
		mindd -= 1
	elif a>dd:
		if maxdd >0:
			ans += a - (dd+1) 
			maxdd -= 1
		else:
			ans ++ a - dd
			mindd -= 1
print(ans)


def main():
    def solve2():
        a = m[:]
        cnt = 0
        t = 1 if Sum % n else 0
        while max(a) - min(a) != t:
            mn = a.index(min(a))
            mx = a.index(max(a))
            a[mn] += 1
            a[mx] -= 1
            cnt += 1
        return cnt
    n = int(input())
    m = list(map(int, input().split()))
    Sum = sum(m)
    mid = Sum // n
    if Sum % n == 0:
        ans = sum(abs(i - mid) for i in m) // 2
    else:
        cntscd = Sum % n
        cnt = ans = 0
        for i in m:
            if i > mid and cnt < cntscd:
                cnt += 1
                ans += i - mid - 1
            else:
                ans += abs(mid - i)
        ans += cntscd - cnt
        ans = ans // 2
    print(ans)
main()


n = int(input())
servers = list(map(int, input().split()))
s = sum(servers)
m = s // n
mod = s % n
total = 0
servers.sort()
for i in range(n - 1, n - mod - 1, - 1):
    total += abs(servers[i] - m - 1)
for i in range(n - mod - 1, -1, -1):
    total += abs(servers[i] - m)
print(total // 2)

import math

n = int(input())
m = input().split()

end = []

for i in range(len(m)):
    m[i] = int(m[i])

min_req = math.floor(sum(m)/len(m))
remainder = sum(m) % len(m)

m.sort()

for i in range(len(m)):
    end.append(min_req)

for i in range(remainder):
    end[i] += 1

end.sort()

counter = 0

for i in range(len(m)):
    counter += abs(m[i] - end[i])

counter /= 2

print(int(counter))

from math import *
n=int(input())
a=list(map(int,input().split(' ')))
b=[]
x=0;y=0;sm=0;k=0;o=0
for i in range(n):
    sm+=a[i]
k=sm//n
for i in range(n):
    b.append(k)
    if (i<sm%n):
        b[i]+=1
a.sort()
b.sort()
for i in range(n):
    o+=abs(a[i]-b[i])
print(o//2)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

n   = int(input())
m   = [int(i) for i in input().split()]

start = time.time()

s = divmod(sum(m),n)[0]

a1 = 0
a2 = 0

for i in m:
    if i < s:
        a1 += s-i

    if i > s+1:
        a2 += i-s-1
print(max(a1, a2))
finish = time.time()
#print(finish - start)


from math import *
n=int(input())
a=list(map(int,input().split(' ')))
b=[]
x=0;y=0;sm=0;k=0;o=0
for i in range(n):
    sm+=a[i]
k=sm//n
for i in range(n):
    b.append(k)
    if (i<sm%n):
        b[i]+=1
a.sort()
b.sort()
for i in range(n):
    o+=abs(a[i]-b[i])
print(o//2)

n = int(input())
a =  list(map(int, input().split()))
s = sum(a)
l = s // n
if s % n == 0:
    r = l
else:
    r = l + 1
k1 = k2 = 0
for x in a:
    if x < l:
        k1 += l - x
    elif x > r:
        k2 += x - r
print(max(k1,k2))


n = int(input())
servers = list(map(int, input().split()))
Sum = sum(servers)
average = Sum//n
flag = Sum%n == 0
ans = 0
cnt = 0
for i in range(n):
	if servers[i] <= average:
		ans += average - servers[i]
		cnt += 1
left = n - cnt
if not flag:
	ans += max(Sum%n - left, 0)

print(ans)