Description

There are $n$ children sitting in a circle, each with $a_i$ candies. Each child can only pass candies to their left and right neighbors. The cost of passing one candy each time is $1$.

Input Format

The first line contains $n$. Each of the next $n$ lines contains $a_i$.

Output Format

Output the minimum cost to make all children have the same number of candies.

4
1
2
5
4

4

Hint

Constraints: For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le a_i \le 1.5 \times 10^9$, and $\sum_{i=1}^{n}{a_i}$ is a multiple of $n$.

Translated by ChatGPT 5