题目描述

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

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

10
1
0
0
2
0
0
1
2
2
2

输出样例

33