Flatten

$N$ piles of chips are placed in a row, and each pile contains zero or more chips. The piles are numbered $1$ through $N$ from left to right.

In one move you pick a pile $p$ and an integer $m$, then transfer $m$ chips from pile $p$ to each of its neighboring piles.

• If $1 < p < N$, pile $p$ has two neighbors, $p-1$ and $p+1$.
• If $p = 1$, its only neighbor is pile $2$.
• If $p = N$, its only neighbor is pile $N-1$.

To perform a move, a pile with two neighbors must hold at least $2m$ chips (it sends $m$ to each side), and a pile with only one neighbor must hold at least $m$ chips.

By repeating such moves, the goal is to flatten the piles, that is, to make every pile hold the same number of chips.

A single move transfers $2m$ chips when the chosen pile has two neighbors, and $m$ chips when it has only one neighbor. Determine the minimum total number of chips that must be transferred to flatten all piles.

Figure 1. Five piles with 0, 7, 8, 1 and 4 chips.	Figure 2. The same piles after the move $p=2$, $m=2$.

• The first line contains the number of piles $N$.
• The second line contains $N$ integers; the $i$-th of them is $C_i$, the number of chips in pile $i$.

• Print a single integer: the minimum total number of chips that must be transferred to flatten all piles.

• $2 \le N \le 200$
• $0 \le C_i \le 2000$, where $C_i$ is the number of chips in pile $i$ at the start ($1 \le i \le N$).
• The total number of chips is a multiple of $N$, and it is guaranteed that the piles can always be flattened.