题目描述

作为当代建筑的粉丝，农夫约翰建造了一个完美圆形的新谷仓。

在内部，谷仓由 $\red{n }$个房间组成，从谷仓周边的 $\red{1…}$$\red{n }$顺时针编号 $\red{(3≤}$$\red{n≤}$$\red{1000)}$。

每个房间都有通往两个相邻房间的门，还有一扇通往谷仓外部的门。农夫约翰拥有 $\red{n }$头奶牛，他希望在谷仓的每个房间里只放 一头奶牛。然而，有些困惑的奶牛在门口随意排着队，可能有多头奶牛在同一个门口排着队。

恰好 $\red{ci }$奶牛在房间 $\red{i }$的门外排队，所以$\red{ ∑ci=n}$。

为了管理放牧奶牛的过程，让每个房间里都有一头奶牛，$\red{Farmer John }$想要使用以下方法：每头奶牛从她最初排队的门进入，然后顺时针穿过房间，直到她到达一个合适的目的地。

假设一头奶牛穿过 $\red{d }$扇门消耗 $\red{d2 }$能量，请确定分配奶牛所需的最小能量，这样一头奶牛最终进入每个房间。

输入格式

第一行输入包含$\red{n}$。

剩余的每个$\red{n}$行包含$\red{c1…}$$\red{cn.}$

输出格式

请写出奶牛消耗的最小能量。

样例

输入样例

10
1
0
0
2
0
0
1
2
2
2

输出样例

33