Circular Barn (Gold)#10586
Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of rooms, numbered clockwise from to around the perimeter of the barn. Each room has doors connecting it to its two neighboring rooms, as well as a door leading to the outside of the barn.
Farmer John owns cows, and he wants exactly one cow to end up in each room of the barn. However, the cows, being slightly confused, line up at random doors, with possibly multiple cows lining up at the same door. Precisely c_i cows line up outside the door to room , so \sum c_i = n.
To manage the process of herding the cows so that exactly one cow ends up in each room, Farmer John uses the following approach: each cow enters through the door where she initially lined up and then walks clockwise through the rooms until she reaches her destination. If a cow walks through doors, she consumes d^2 units of energy. Please determine the minimum total amount of energy required to distribute the cows so that exactly one cow ends up in each room.
The first line contains one integer n~(3 \le n \le 10^6). The next lines each contain an integer c_i~(0 \le c_i \le n), where \sum c_i = n.
Print the minimum total amount of energy consumed by the cows.
Example 1