Amateur d’architecture contemporaine, Farmer John a construit une étable parfaitement circulaire. Elle comporte un anneau de $n$ pièces, numérotées dans le sens horaire $1 \ldots n$ le long du pourtour ($3 \leq n \leq 100,000$). Chaque pièce a une porte vers chacune de ses deux voisines et une porte extérieure.

Il possède $n$ vaches et veut exactement une vache par pièce. Mais, un peu confuses, elles font la queue devant des portes quelconques, parfois plusieurs devant la même. Il y a exactement $c_i$ vaches devant la porte extérieure de la pièce $i$, donc $\sum c_i = n$.

Chaque vache entre par la porte où elle attendait, puis parcourt les pièces dans le sens horaire jusqu’à une destination appropriée. Traverser $d$ portes consomme $d^2$ unités d’énergie. Déterminez l’énergie totale minimale pour placer une vache dans chaque pièce.

Entrée

La première ligne contient $n$. Les $n$ suivantes contiennent, un par ligne et dans l’ordre, $c_1 \ldots c_n$.

Sortie

Affichez l’énergie totale minimale consommée par les vaches.

Exemples

Entrée 1

10
1
0
0
2
0
0
1
2
2
2

Sortie 1

33

Auteur : Brian Dean