평탄화

$N$개의 더미가 한 줄로 놓여 있고, 각 더미에는 0개 이상의 칩이 들어 있다. 더미는 왼쪽부터 $1$번, $2$번, ..., $N$번으로 번호가 매겨진다.

한 번의 이동(move) 이란 더미 하나 $p$와 정수 $m$을 골라, 더미 $p$에서 이웃한 각 더미로 칩을 $m$개씩 옮기는 것이다.

• $1 < p < N$ 이면 더미 $p$의 이웃은 $p-1$과 $p+1$, 두 개다.
• $p = 1$ 이면 이웃은 $2$번 더미 하나뿐이다.
• $p = N$ 이면 이웃은 $N-1$번 더미 하나뿐이다.

따라서 이웃이 둘인 더미에서 이동하려면 양쪽에 $m$개씩 보내야 하므로 더미 $p$에 칩이 최소 $2m$개 있어야 하고, 이웃이 하나뿐인 더미에서는 최소 $m$개 있어야 한다.

이런 이동을 반복하여 모든 더미의 칩 개수를 같게 만드는 것, 즉 더미를 평탄화하는 것이 목표다.

한 번의 이동으로 옮겨지는 칩의 수는 이웃이 둘인 더미에서는 $2m$개, 이웃이 하나인 더미에서는 $m$개다. 모든 더미를 평탄화하기 위해 옮겨야 하는 칩의 최소 총 개수를 구하여라.

그림 1. 칩이 각각 0, 7, 8, 1, 4개 있는 다섯 더미.	그림 2. 이동 $p=2$, $m=2$ 를 수행한 뒤의 같은 더미.

• 첫째 줄에 더미의 개수 $N$이 주어진다.
• 둘째 줄에 $N$개의 정수가 주어지며, 그중 $i$번째는 $i$번 더미의 칩 개수 $C_i$이다.

• 모든 더미를 평탄화하기 위해 옮겨야 하는 칩의 최소 총 개수를 한 줄에 출력한다.

• $2 \le N \le 200$
• $0 \le C_i \le 2000$ (게임 시작 시 $i$번 더미의 칩 개수, $1 \le i \le N$)
• 모든 칩의 합은 $N$의 배수이며, 항상 평탄화가 가능함이 보장된다.