Summary

This is similar to “Stacks of Bricks” except that for each move you are only allowed to move a brick to a stack on its immediate left or right.

Problem statement

You are given a sequence of n (n < 100) integers. Each number denotes the height of a stack of bricks. If we put the stacks in a line as in the illustration below, we would see stacks of uneven heights. Suppose a “move” is made by picking up one brick from one stack and putting it on stack to its immediate left or right, compute the minimum number of moves to rearrange the bricks such that all stacks have the same height.

Read the input from standard input. The first line of the input is the integer n, followed by n lines of integers denoting the height of the n stacks. The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height. Your output to standard output should consist of exactly one integer denoting the minimum number of moves.

Sample input

6
5
2
4
1
7
5

Sample output

8