Farmer John, aficionado a la arquitectura contemporánea, construyó un establo perfectamente circular. Dentro hay un anillo de $n$ habitaciones, numeradas en sentido horario $1 \ldots n$ alrededor del perímetro ($3 \leq n \leq 100,000$). Cada habitación tiene puertas a sus dos vecinas y una al exterior.

Tiene $n$ vacas y quiere exactamente una en cada habitación. Pero, algo confundidas, hacen cola ante puertas al azar, posiblemente varias ante la misma. Hay exactamente $c_i$ vacas ante la puerta exterior de la habitación $i$, así que $\sum c_i = n$.

Cada vaca entra por la puerta ante la que esperaba y camina en sentido horario por las habitaciones hasta un destino adecuado. Atravesar $d$ puertas consume $d^2$ de energía. Encuentra la mínima energía total para colocar una vaca en cada habitación.

Entrada

La primera línea contiene $n$. Las siguientes $n$ contienen $c_1 \ldots c_n$ en orden, uno por línea.

Salida

Imprime la mínima energía total consumida por las vacas.

Ejemplos

Entrada 1

10
1
0
0
2
0
0
1
2
2
2

Salida 1

33

Autor: Brian Dean