Cubes
On his nephew Petryk's birthday, Stepan gave him a set of blocks. Petryk immediately began constructing a fence with these blocks, but the columns he built ended up having different heights. This piqued Stepan's curiosity: "What is the minimum number of moves required to ensure that the height difference between any two columns is no more than one block? Note that only one block can be moved at a time from one column to an adjacent column."
Input
The first line of the input contains the integer N (1 ≤ N ≤ 1000), representing the number of columns of blocks Petryk has. The second line contains N integers, each indicating the height of a column in blocks. All heights are no greater than 10^6.
Output
The output should be a single integer, representing the minimum number of block moves needed so that the height difference between any two columns is at most one block.
Example Explanation
Move two blocks from column #3 to column #4. The result is 3 4 6 4 5. Then, move one block from column #2 to column #1. The result is 4 3 6 4 5. Finally, move one block from column #3 to column #2. The result is 4 4 5 4 5.