Boxes

Interview

Time limit1sMemory limit128 MB

Summary

Boxes stand in a circle with at most n balls total; move balls to neighbors so each box holds at most one, minimizing the number of moves.

Level: Medium7 of 10
Topics: Greedy, Prefix sum, Math, Implementation
Solved: No attempts yet

Problem

There are $n$ boxes arranged in a circle, numbered from $1$ to $n$ in clockwise order ( $1 \le n \le 1000$ ). Because the boxes form a circle, box $1$ and box $n$ are also neighbors. Some boxes contain balls, and the total number of balls is at most $n$ .

You want to rearrange the balls so that every box holds at most one ball. In one move you may shift a single ball from a box to one of its two neighboring boxes.

Write a program that computes the minimum number of moves needed so that each box holds at most one ball.

Input

The first line contains the number of boxes $n$ . Each of the next $n$ lines contains one nonnegative integer; the integer on the $i$ -th of these lines is the number of balls in box $i$ . The total number of balls is at most $n$ .

Output

Print a single nonnegative integer: the minimum number of moves needed so that each box holds at most one ball.

Examples5

Example 1
Input
```
12
0
0
2
4
3
1
0
0
0
0
0
1
```
Expected output
```
19
```
Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
1
1
```
Expected output
```
0
```
Example 4
Input
```
2
2
0
```
Expected output
```
1
```
Example 5
Input
```
3
3
0
0
```
Expected output
```
2
```