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