Circle Candy Redistribution

There are n children sitting in a circle. Each child has a_i candies. A child can only pass a candy to his/her immediate left or right neighbor, and each candy transfer costs 1 unit. The goal is to redistribute the candies so that every child ends up having the same number of candies.

Note: It is only possible to equalize the candies if the total number of candies is divisible by n. Otherwise, output -1.

Mathematical Formulation:

Let \(T = \frac{\sum_{i=1}^{n} a_i}{n}\) be the target number of candies per child (if it is an integer). Define \(d_i = a_i - T\). Since redistributions can only occur between adjacent children in a circle, one effective method is to compute a prefix sum array (after choosing an arbitrary breaking point in the circle):

\[ S_0 = 0, \quad S_i = \sum_{j=1}^{i} d_j \quad \text{for } 1 \le i \le n-1, \quad \text{and } S_n = 0. \]

The minimal total cost required is given by:

\[ \text{Cost} = \sum_{i=0}^{n-1} \left|S_i - m\right|, \]

where (m) is the median of ({S_0, S_1, \ldots, S_{n-1}}). This formula works since moving a candy from one child to its neighbor adjusts the prefix sums, and the sum of the absolute deviations from a central median minimizes the cost.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of children. The second line contains n space-separated integers: a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹), representing the number of candies each child initially has.

outputFormat

Output a single integer representing the minimum total cost required to equalize the candies among all children. If it is impossible to do so, output -1.

sample

4
2 2 2 2

0