Appassionato di architettura contemporanea, Farmer John ha costruito una stalla perfettamente circolare. Dentro ci sono $n$ stanze in un anello, numerate in senso orario $1 \ldots n$ lungo il perimetro ($3 \leq n \leq 100,000$). Ogni stanza ha porte verso le due vicine e una verso l’esterno.

Ha $n$ mucche e vuole esattamente una per stanza. Ma, un po’ confuse, fanno la fila davanti a porte casuali, anche più mucche alla stessa. Davanti alla porta esterna della stanza $i$ ci sono esattamente $c_i$ mucche, quindi $\sum c_i = n$.

Ogni mucca entra dalla porta dove era in fila, poi cammina in senso orario tra le stanze fino a una destinazione adatta. Attraversare $d$ porte consuma $d^2$ di energia. Trova la minima energia totale per sistemare una mucca in ogni stanza.

Input

La prima riga contiene $n$. Le successive $n$ contengono $c_1 \ldots c_n$ in ordine, uno per riga.

Output

Stampa la minima energia totale consumata dalle mucche.

Esempi

Input 1

10
1
0
0
2
0
0
1
2
2
2

Output 1

33

Autore: Brian Dean