Circular Barn Energy Optimization

Farmer John has built a new circular barn with (n) rooms arranged in a circle ((3 \le n \le 10^5)) in clockwise order, numbered (1,2,\dots,n). Each room has doors connecting it to its two adjacent rooms (on the left and right) as well as one door to the outside. John has (n) cows and wants exactly one cow in each room. Unfortunately, the cows are distributed arbitrarily – the (i)th room initially contains (c_i) cows, and it is guaranteed that (\sum_{i=1}^{n} c_i = n).

To solve this, John uses the following strategy: he chooses some cows to move clockwise (possibly through several rooms) until every room contains exactly one cow. If a cow passes through (d) doors, it expends (d^2) units of energy. Your task is to compute the minimum total energy consumed by all the cows if John moves them optimally.

A useful way to think about the problem is as follows. For every room (i), define the imbalance (b_i = c_i - 1). Then, if we define the prefix sum (starting with (f_0 = 0)) [ f_i = \sum_{j=1}^{i} (c_j - 1) \quad \text{for } i=1,2,\dots,n-1, ] and let (m = \min_{0 \le i < n} f_i), it turns out that the optimal total energy is given by [ \text{Energy} = \sum_{i=0}^{n-1} (f_i - m)^2. ] Note that by the problem constraints we have (f_n = 0).

The answer you compute should be an integer.

inputFormat

The first line contains an integer (n) (the number of rooms and cows). The second line contains (n) space‐separated integers (c_1, c_2, \dots, c_n) where (c_i) represents 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 consumed by the cows.

sample

3
0 2 1

2