Circular Barn Energy Minimization

Farmer John built a new circular barn with n rooms arranged in a circle (3 ≤ n ≤ 1000), numbered 1 through n in clockwise order. Each room has doors to its two adjacent rooms (left and right) as well as a door leading outside.

There are exactly n cows in total, but unfortunately the cows are scattered arbitrarily. Specifically, room i contains c_i cows, and it is guaranteed that \(\sum_{i=1}^{n} c_i = n\). Farmer John wants to redistribute the cows so that each room ends up with exactly one cow.

To achieve this, he will instruct some cows to move clockwise through the rooms. If a cow passes through d doors, the energy consumed by that cow is \(d^2\). Your task is to compute the minimal total energy consumed by all cows under an optimal redistribution strategy.

Hint: One way to solve the problem is to consider the prefix imbalances \(P[i] = \sum_{j=1}^{i} (c_j - 1)\). A rotation of the barn corresponds to subtracting a constant from each prefix sum. The optimal solution minimizes \(\sum (P[i] - m)^2\) over an appropriate choice of constant \(m\), which turns out to be the median of the prefix sums.

inputFormat

The first line contains a single integer n (3 ≤ n ≤ 1000), the number of rooms (and cows) in the barn.

The next n lines each contain a single integer c_i (0 ≤ c_i ≤ n) indicating the number of cows initially in room i. It is guaranteed that \(\sum_{i=1}^{n} c_i = n\).

outputFormat

Output a single integer, the minimum total energy required to redistribute the cows so that each room contains exactly one cow.

sample

3
2
0
1

1