Description

Original source: HAOI 2008

There are $n$ children sitting in a circle, each with $a_i$ candies. Each child can only pass candies to their immediate left or right neighbors. The cost of passing one candy is $1$. Find the minimum total cost to make all children have an equal number of candies.

Input Format

The first line contains an integer $n$, the number of children;

The next $n$ lines each contain an integer $a_i$.

Output Format

Output the minimum total cost to make all children have an equal number of candies.

Sample 1

4
1
2
5
4

4

Constraints & Hints

For $30\%$ of the data, $n \leq 1000$;

For $100\%$ of the data, $n \leq 10^6$, and it is guaranteed that the answer can be stored in a 64-bit signed integer.