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?
The first line contains integer *n* (1 ≤ *n* ≤ 50000). The second line contains *n* non-negative numbers that do not exceed 10<sup class="upper-index">9</sup>, 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*.
n=int(input())
lst=[*map(int,input().split())]
item=sum(lst)//n
if n==1:
    from sys import exit
    print(0);exit()
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
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)