There are n
boxes in a row. Each box contains Ki beads. It is
known that the total number of beads is a multiple of n. On each
move a single bead can be moved from its box to an adjacent box (to the left or
to the right). Obviously, there exists a sequence of moves that will result in
the same number of beads in each box.
Write a program
to determine the minimum number of moves leading to equal number of beads in
all boxes.
Limitations
1 <=
n <= 100 000; 0
<= Ki <= 100 000.
Input
The first line
contains an integer n. The following line contain numbers Ki.
Output
The output file
must specify a single integer, the minimum possible number of moves leading to
equal number of beads in all boxes.
Sample
|
Standard input
|
Standard output
|
|
5
4 1 3 2
5
|
5
|
