Farmer John 喜愛現代建築，建了一座完全圓形的新牛棚。牛棚內有環狀排列的 $n$ 個房間，沿周邊順時針編號為 $1 \ldots n$（$3 \leq n \leq 100,000$）。每個房間都有通往兩個相鄰房間的門，每個相鄰房間各一扇，還有一扇通向牛棚外的門。

Farmer John 有 $n$ 頭乳牛，希望最終每個房間恰有一頭。但乳牛有些迷糊，隨意在各扇門前排隊，同一扇門前可能有多頭。房間 $i$ 的外門前恰有 $c_i$ 頭乳牛，因此 $\sum c_i = n$。

為把乳牛分配到各房間，他採用如下方式：每頭乳牛從最初排隊的門進入，隨後順時針穿過房間，直到合適的目的地。穿過 $d$ 扇門消耗 $d^2$ 能量。求使每個房間最終恰有一頭乳牛所需的最小總能量。

輸入格式

第一行包含 $n$。接下來 $n$ 行依次包含 $c_1 \ldots c_n$，每行一個。

輸出格式

輸出乳牛消耗的最小總能量。

範例

輸入格式 1

10
1
0
0
2
0
0
1
2
2
2

輸出格式 1

33

題目作者：Brian Dean