K. Kavala Olives
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

At a taverna in Kavala, a cook is arranging olives on small plates for dinner. The cook wants to distribute the olives so that no plate contains more than one.

There are $$$n$$$ plates arranged in a circle and numbered from $$$1$$$ to $$$n$$$ in clockwise order. Plate $$$i$$$ initially contains $$$a_i$$$ olives. The total number of olives does not exceed $$$n$$$.

In one move, you may take one olive from a plate and put it onto the next plate clockwise or counterclockwise. In particular, plates $$$1$$$ and $$$n$$$ are adjacent. There is no limit on the number of olives on a plate during the process.

Find the minimum number of moves needed to make every plate contain at most one olive.

Input

The first line contains an integer $$$n$$$ ($$$1\le n\le 200\,000$$$), the number of plates.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le n$$$), the initial numbers of olives. It is guaranteed that $$$a_1+a_2+\cdots+a_n\le n$$$.

Output

Print one integer: the minimum number of moves.

Examples
Input
6
3 0 0 0 0 0
Output
2
Input
5
1 0 1 0 1
Output
0
Input
5
0 3 2 0 0
Output
4
Note

In the first example, move one olive from plate $$$1$$$ to plate $$$2$$$, and another olive from plate $$$1$$$ to plate $$$6$$$. Two moves are necessary because two olives must leave plate $$$1$$$.

In the second example, every plate already contains at most one olive.

In the third example, move two olives from plate $$$2$$$ to plate $$$1$$$, one at a time. Then move one olive from plate $$$1$$$ to plate $$$5$$$, and one from plate $$$3$$$ to plate $$$4$$$. This takes four moves; a plate may temporarily contain more than one olive.