Farmer John, fã de arquitetura contemporânea, construiu um estábulo perfeitamente circular. Dentro há um anel de $n$ salas, numeradas no sentido horário $1 \ldots n$ ao redor do perímetro ($3 \leq n \leq 100,000$). Cada sala tem portas para as duas vizinhas e uma para fora.

Ele tem $n$ vacas e quer exatamente uma em cada sala. Porém, um pouco confusas, elas fazem filas diante de portas aleatórias, possivelmente várias na mesma. Há exatamente $c_i$ vacas diante da porta externa da sala $i$, portanto $\sum c_i = n$.

Cada vaca entra pela porta onde esperava e caminha no sentido horário pelas salas até um destino apropriado. Passar por $d$ portas consome $d^2$ de energia. Determine a energia total mínima para colocar uma vaca em cada sala.

Entrada

A primeira linha contém $n$. As próximas $n$ contêm $c_1 \ldots c_n$ em ordem, um valor por linha.

Saída

Imprima a energia total mínima consumida pelas vacas.

Exemplos

Entrada 1

10
1
0
0
2
0
0
1
2
2
2

Saída 1

33

Autor: Brian Dean