Cubes#7676
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."
The first line of the input contains the integer (1 \leq N \leq 1000), representing the number of columns of blocks Petryk has. The second line contains integers, each indicating the height of a column in blocks. All heights are no greater than 10^6.
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 1
Move two blocks from column #3 to column #4. The result is . Then, move one block from column #2 to column #1. The result is . Finally, move one block from column #3 to column #2. The result is .