Boxes

Memory limit: 32 MB

There are boxes on the circle. The boxes are numbered from to () in clockwise order. There are balls in the boxes, and the number of all the balls in the boxes is not greater than . The balls should be displaced in such a way that in each box there remains no more than one ball. In one move we can shift a ball from one box to one of it's neighboring boxes.

Task

Write a program that:

• reads from the standard input the number of boxes and the arrangement of balls in the boxes,
• computes the minimal number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball,
• writes the result to the standard output.

Input

In the first line of the standard input there is written one positive integer — the number of boxes. In each of the following lines there is written one nonnegative integer. In the -th of these lines there is written the number of balls in the -th box.

Output

Your program should write to the standard output one nonnegative integer — the number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball.

Example

For the input data:

12
0
0
2
4
3
1
0
0
0
0
0
1

the correct result is:

19

Task author: Krzysztof Diks.