P2512 [HAOI2008] Candy Passing

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$.

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

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

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