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: MEDIUM_HARD
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from array import array
n = int(input())
a = [int(v) for v in input().split()]
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())
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())
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())
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)


import itertools
n = int(input())
a = 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)


from itertools import accumulate
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
s = sum(l)
q = s // n
extras = []
extraind = []
lackee = []
for (i, e) in enumerate(l):
	if e > q:
		extras.append(e - q)
		extraind.append(i)
	elif e < q:
		lackee.append((i, q - e))
c = 0
i = 0
for (indx, e) in lackee:
	s = 0
	while s < e:
		nextra = max(0, extras[i] - (e - s))
		s += extras[i] - nextra
		c += (extras[i] - nextra) * abs(indx - extraind[i])
		extras[i] = nextra
		if extras[i] == 0:
			i += 1
print(c)


n = int(input())
a = list(map(int, input().split()))
need = sum(a) // n
ans = 0
from math import *
for i in range(n - 1):
	if a[i] <= need:
		a[i + 1] -= need - a[i]
	else:
		a[i + 1] += a[i] - need
	ans += abs(a[i] - need)
print(ans)


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)


def read(mode=2):
	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='')
(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)


from sys import stdin as cin, stdout as cout
from math import factorial as f
from itertools import combinations as comb
n = int(cin.readline())
a = list(map(int, cin.readline().split()))
k = int(sum(a) / n)
sum = 0
for i in range(n - 1):
	sum += abs(a[i] - k)
	a[i + 1] = a[i + 1] - (k - a[i])
print(sum)


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)


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())
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())
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())
a = [int(x) for x in input().split()]
s = sum(a) // n
lft = 0
ans = 0
for i in range(n):
	ans += abs(lft)
	lft += a[i] - s
print(ans)


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)


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())
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 = list(map(int, input().split()))
sum = 0
for x in a:
	sum += x
t = sum // n
ans = 0
for i in range(n - 1):
	if a[i] < t:
		ans += t - a[i]
		a[i + 1] -= t - a[i]
	else:
		ans += a[i] - t
		a[i + 1] += a[i] - t
print(ans)


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


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)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right
import bisect
n = int(input())
arr = list(map(int, input().split()))
final = sum(arr) // n
s = 0
ans = 0
for i in range(n):
	s += arr[i] - final
	ans += abs(s)
print(ans)


n = int(input())
a = list(map(int, input().split())) + [0]
s = sum(a) // n
d = 0
for i in range(n):
	if a[i] > s:
		a[i + 1] += abs(a[i] - s)
	else:
		a[i + 1] -= abs(a[i] - s)
	d += abs(a[i] - s)
print(d)


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)