Description

As an enthusiast of modern architecture, Farmer John built a new circular barn. Inside the barn, $n$ rooms are arranged in a ring ($3 \leq n \leq 1000$), numbered in clockwise order $1\ldots n$. Each room has doors to its two adjacent rooms, as well as a door to the outside.

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

FJ decides to solve this by letting some cows move clockwise through rooms to their designated positions. If a cow passes through $d$ doors, it expends $d^2$ energy. You need to compute the minimal possible total energy expended by all cows.

Input Format

The first line contains an integer $n$. The next $n$ lines each contain one integer $c_i$, where the $i$-th line contains $c_i$.

Output Format

Output the minimal total energy expended by all cows.

10
1
0
0
2
0
0
1
2
2
2

33

Hint

Translated by ChatGPT 5