Petya has k matches, placed in n matchboxes lying in a line from left to right. We know that k is divisible by n. Petya wants all boxes to have the same number of matches inside. For that, he can move a match from its box to the adjacent one in one move. How many such moves does he need to achieve the desired configuration?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 50000). The second line contains n non-negative numbers that do not exceed 10^9, the i-th written number is the number of matches in the i-th matchbox. It is guaranteed that the total number of matches is divisible by n.


-----Output-----

Print the total minimum number of moves.


-----Examples-----
Input
6
1 6 2 5 3 7

Output
12

Difficulty: interview

Starter code:

Solutions:
"""
Codeforces Testing Round 10 Problem B

Author  : chaotic_iak
Language: Python 3.3.4
"""

def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0:
        return inputs
    if mode == 1:
        return inputs.split()
    if mode == 2:
        return [int(x) for x in inputs.split()]

def write(s="\n"):
    if isinstance(s, list): s = " ".join(s)
    s = str(s)
    print(s, end="")

################################################### SOLUTION
n, = read()
a = read()
s = sum(a) // n
r = 0
for i in range(n-1):
    if a[i] < s:
        r += s - a[i]
        a[i+1] -= s - a[i]
    else:
        r += a[i] - s
        a[i+1] += a[i] - s
print(r)

import itertools

n = int(input())

a = list(map(int, input().split()))
a = list(itertools.accumulate(a))

need_one = a[-1] // n

ans = 0
for i in range(len(a) - 1):
	ans += abs((i + 1) * need_one - a[i])

print(ans)


n = int(input())
a = list(map(int, input().split()))

k = int(sum(a)/n)
summ = 0
for i in range(n-1):
	summ += abs(a[i]-k)
	a[i+1] = a[i+1]-(k-a[i])
print(summ)

n = int(input())
boxs = list(map(int,input().split()))

tot = sum(boxs)
num = tot // n

s = 0
for i in range(n-1):
    if boxs[i] < num :
        
        boxs[i+1] = boxs[i+1] - (num - boxs[i])
        s += num - boxs[i]
        boxs[i] = num
    elif boxs[i] > num :
        boxs[i+1] = boxs[i+1] + (boxs[i] - num)
        s += boxs[i] - num
        boxs[i] = num
print(int(s))

n = int(input())
boxs = list(map(int,input().split()))

tot = sum(boxs)
num = tot // n

s = 0
for i in range(n-1):
    if boxs[i] < num :
        
        boxs[i+1] = boxs[i+1] - (num - boxs[i])
        s += num - boxs[i]
        boxs[i] = num
    elif boxs[i] > num :
        boxs[i+1] = boxs[i+1] + (boxs[i] - num)
        s += boxs[i] - num
        boxs[i] = num
    #print(boxs)
print(int(s))


n = int(input())
a = list(map(int, input().split()))
k = sum(a)
s = 0
r = 0
for i in range(n):
  s += k // n - a[i]
  r += abs(s)
print(r)

n = int(input())

x = list(map(int, input().split(" ")))

zap = sum(x) // n

alr = 0
res = 0
for ele in x:
  alr += zap - ele
  res += abs(alr)
print(res)

n=int(input())
a=list(map(int,input().split()))
k=0
for i in range(n):
	k+=a[i]
aver=k//n
h=0
x=0
y=1
s=0
for i in range(n):
  s += aver - a[i]
  h += abs(s)
print(h)


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

S = sum(a)
final = S // n

result = 0
for i in range(len(a) - 1):
    result += abs(a[i] - final)
    a[i + 1] += a[i] - final

print(result)


n = int(input())
t = list(map(int, input().split()))
s, k = 0, sum(t) // n
t = [i - k for i in t]
for i in range(n - 1):
    s += abs(t[i])
    t[i + 1] += t[i]
print(s)

n = int(input())
xs = list(map(int, input().split()))
u = sum(xs)//n

moves = 0
for i in range(n-1):
    moves += abs(u-xs[i])
    xs[i+1] += xs[i]-u

print(moves)

n = int(input())
t = list(map(int, input().split()))
s = sum(t)//n
t = [i-s for i in t]
r = 0
for i in range(len(t) - 1):
    t[i+1] += t[i]
    r += abs(t[i])

print(r)

3
from array import array
n = int(input())
a = [int(v) for v in input().split()]
#a = array("l")
#a.fromlist(t)
s = 0
k = sum(a)
m = int(k/n)
for i in range(n-1):
    d = m - a[i]
    a[i] = m
    a[i+1] -= d
    s += abs(d)
print(s)


n = int(input())
a = [int(i) for i in input().split()]
av = sum(a) // len(a)
ans = 0
s = 0
for i in a:
    s += i - av
    ans += abs(s)
print(ans)

a=[]

def main():
	n=int(input())
	a.append(0)
	B=input()
	for x in B.split():
		a.append(int(x))
	a.append(0)
	S=sum(a)
	ave=int(S/n)
	ans=0
	for i in range(1,n+1,1):
		if a[i] < ave:
			ans += ave-a[i]
			a[i+1] -= ave-a[i]
		else:
			ans += a[i]-ave
			a[i+1] += a[i]-ave
	print(ans)

main()

n = int(input())
a = [int(i) for i in input().split()]
s = 0
for i in a:
    s += i
m = s // n
ans = 0
for i in range(n - 1):
    ans += abs(m - a[i])
    if a[i] < m:
        a[i + 1] -= m - a[i]
    else:
        a[i + 1] += a[i] - m
print(ans)

#from dust i have come dust i will be

n=int(input())
a=list(map(int,input().split()))

t=0
for i in range(n):
    t+=a[i]

t=t//n
cnt=0

for i in range(n):
    if a[i]>t:
        a[i+1]+=abs(a[i]-t)
        cnt+=(abs(a[i]-t))

    elif a[i]<t:
        a[i+1]-=abs(a[i]-t)
        cnt+=(abs(a[i]-t))

print(cnt)




#from dust i have come dust i will be

n=int(input())
a=list(map(int,input().split()))

t=0
for i in range(n):
    t+=a[i]

t=t//n
cnt=0

for i in range(n):
    if a[i]>t:
        a[i+1]+=abs(a[i]-t)
        cnt+=(abs(a[i]-t))

    elif a[i]<t:
        a[i+1]-=abs(a[i]-t)
        cnt+=(abs(a[i]-t))

print(cnt)



n = int(input())

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

av = sum(a) // len(a)

ans = 0

s = 0

for i in a:

    s += i - av

    ans += abs(s)

print(ans)



# Made By Mostafa_Khaled


x = int( input() )

a = list( map( int, input().strip().split( ' ' ) ) )
count = 0
sum = 0
for i in range( len( a ) ):
    sum += a[i]
z = int( sum / x )

for i in range( len( a ) ):
    if a[i] != z and a[i] > z:
        b = abs( z - a[i] )
        a[i] = a[i] - b
        count += b
        a[i+1] +=b

    if a[i] != z and a[i] < z:
        b = abs( z - a[i] )
        a[i] = a[i] + b
        count += b
        a[i+1] -=b
print( count )

n = int(input())
s = [int(i) for i in input().split()]
k = sum(s)//n
c = 0
for i in range(0,len(s)-1):
    if s[i] == k :
        continue
    need = k-s[i]
    s[i+1] -= need
    c += abs(need)
print(c)


n=int(input())
lst=[*map(int,input().split())]
item=sum(lst)//n
if n==1:print(0);return
less,more,leng1,leng2=[],[],0,0
for i,x in enumerate(lst):
    if x<item:less.append(i);leng1+=1
    if x>item:more.append(i);leng2+=1
if leng1==0 and leng2==0:print(0);return
i,j=0,0
x,y=less[i],more[j]
res=0
while i<leng1 and j<leng2:
    x,y=less[i],more[j]
    elem1=lst[x]
    elem2=lst[y]
    diff1=item-elem1
    diff2=elem2-item
    if diff2>diff1:
        res+=(abs(x-y)*diff1)
        lst[y]-=diff1
        i+=1
    elif diff2<diff1:
        res+=(abs(x-y)*diff2)
        lst[x]+=diff2
        j+=1
    else:
        res+=(abs(x-y)*diff1)
        i,j=i+1,j+1
print(res)