Minimizing Card Movement Cost

After a busy but fulfilling day, little X was about to go to bed when he noticed a row of n piles of cards on his desk. The piles are numbered from 1 to n and the i-th pile contains a_i cards (possibly zero). Recalling the classic problem "Equalizing Cards," little X decided to make a twist: the total number of cards need not be a multiple of n, and the allowed moves and the final goal are modified.

You can move any number of cards from any pile i to any other pile j at a cost of |i-j| per card (where |i-j| is the absolute difference between i and j). The objective is to achieve a configuration where the difference between the pile with the most cards and the pile with the fewest cards is ≤ 1.

In other words, if the total number of cards is T and we define x = \(\lfloor T/n \rfloor\) and r = T \; mod \; n, then in the final configuration exactly r piles should have x+1 cards and the remaining n-r piles should have x cards. Determine the minimum total cost required to achieve such a configuration.

Note: There is no limit on how many cards you may move in a single operation, and moves can be performed between any two piles in any order.

inputFormat

The first line contains a single integer n (the number of piles).

The second line contains n integers: a₁, a₂, ..., a_n.

outputFormat

Output a single integer: the minimum total cost required to achieve the target configuration.

sample

3
2 2 2

0