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.
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$$$.
Print one integer: the minimum number of moves.
63 0 0 0 0 0
2
51 0 1 0 1
0
50 3 2 0 0
4
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.
