Fan współczesnej architektury Farmer John zbudował idealnie okrągłą oborę. W środku jest pierścień $n$ pomieszczeń, ponumerowanych zgodnie z ruchem wskazówek zegara $1 \ldots n$ wokół obwodu ($3 \leq n \leq 100,000$). Każde ma drzwi do obu sąsiadów i na zewnątrz.

Ma $n$ krów i chce dokładnie jedną w każdym pomieszczeniu. Nieco zdezorientowane krowy stoją jednak przy przypadkowych drzwiach, czasem po kilka przy tych samych. Przed zewnętrznymi drzwiami pomieszczenia $i$ stoi dokładnie $c_i$ krów, więc $\sum c_i = n$.

Każda krowa wchodzi przez drzwi, przy których stała, i idzie zgodnie z ruchem wskazówek zegara przez pomieszczenia do odpowiedniego celu. Przejście przez $d$ drzwi zużywa $d^2$ energii. Znajdź minimalną łączną energię potrzebną do rozmieszczenia po jednej krowie w każdym pomieszczeniu.

Wejście

Pierwszy wiersz zawiera $n$. Kolejne $n$ zawiera $c_1 \ldots c_n$ w tej kolejności, po jednej wartości na wiersz.

Wyjście

Wypisz minimalną łączną energię zużytą przez krowy.

Przykład

Wejście 1

10
1
0
0
2
0
0
1
2
2
2

Wyjście 1

33

Autor zadania: Brian Dean