Description

There are $n$ people sitting around a round table. Each person has some number of gold coins, and the total number of coins is divisible by $n$. Each person can give some coins to their left and right neighbors, and in the end everyone must have the same number of coins.

Your task is to find the minimum total number of coins that are passed from hand to hand.

Input Format

The first line contains an integer $n$ ($n \ge 3$).

The next $n$ lines each contain a positive integer, given in counterclockwise order, representing the number of coins each person has.

Output Format

Output one line containing the minimum total number of coins that are passed from hand to hand.

4
1
2
5
4

4

Hint

Sample Explanation

Suppose the four people are numbered $1,2,3,4$. Person $3$ gives person $2$ $2$ coins (becoming $1,4,3,4$). Then person $2$ and person $4$ each give person $1$ $1$ coin.

Constraints

For $100\%$ of the testdata, $3 \le n \le 10^5$, and $total$ $coins \le 10^9$.

Translated by ChatGPT 5