Description

As a fan of modern architecture, Farmer John built a new circular barn. Inside the barn there are $n$ rooms arranged in a ring ($3 \leq n \leq 10^5$), numbered $1 \ldots n$ in clockwise order. Each room has doors to its left and right neighboring rooms, and also a door leading outside.

Now FJ has $n$ cows, and his goal is to have exactly one cow in each room. Unfortunately, the cows are currently in random rooms: room $i$ contains $c_i$ cows. It is guaranteed that $\sum c_i = n$.

FJ decides to solve this problem as follows: he will have some cows move clockwise, passing through some rooms to reach their assigned positions. If a cow passes through $d$ doors, the energy it uses is $d^2$. You need to help FJ compute the minimum possible total energy used by all cows.

Input Format

The first line contains an integer $n$. The next $n$ lines each contain an integer $c_i$ on line $i$.

Output Format

Output the minimum total energy used by all cows.

10
1
0
0
2
0
0
1
2
2
2

33

Hint

Translated by ChatGPT 5