Als Freund moderner Architektur hat Farmer John einen vollkommen runden Stall gebaut. Innen liegen $n$ Räume ringförmig, im Uhrzeigersinn mit $1 \ldots n$ nummeriert ($3 \leq n \leq 100,000$). Jeder Raum hat Türen zu beiden Nachbarräumen und eine nach draußen.

Er besitzt $n$ Kühe und möchte genau eine pro Raum. Die etwas verwirrten Kühe stehen jedoch an beliebigen Türen an, möglicherweise mehrere an derselben. Vor der Außentür von Raum $i$ stehen genau $c_i$ Kühe, daher $\sum c_i = n$.

Jede Kuh tritt durch ihre ursprüngliche Tür ein und läuft im Uhrzeigersinn durch die Räume bis zu einem geeigneten Ziel. Das Durchqueren von $d$ Türen verbraucht $d^2$ Energie. Bestimme die minimale Gesamtenergie, um eine Kuh pro Raum zu verteilen.

Eingabe

Die erste Zeile enthält $n$. Die nächsten $n$ enthalten der Reihe nach $c_1 \ldots c_n$, einen Wert pro Zeile.

Ausgabe

Gib die minimale von den Kühen verbrauchte Gesamtenergie aus.

Beispiele

Eingabe 1

10
1
0
0
2
0
0
1
2
2
2

Ausgabe 1

33

Aufgabenautor: Brian Dean