Description

作为当代建筑的爱好者，农夫约翰建了一座新谷仓，其形状是一个完美的圆形。谷仓内部由 $n$ 间房间组成，沿着谷仓的周边按顺时针方向编号为 $1$ 到 $n$，其中 $3 \leq n \leq 1000$。每个房间都有通往相邻两个房间的门，同时还有一扇通向谷仓外部的门。

农夫约翰希望每个房间 $i$ 中正好有 $r_i$ 头牛，其中 $1 \leq r_i \leq 100$。为了有序地将牛赶进谷仓，他计划解锁某个房间的外部门，让牛从该房间进入。每头牛都会沿顺时针方向穿过房间，直到到达适合的目的地。农夫约翰希望解锁一个房间的外部门，以使所有牛走的总距离最小。请你帮助确定，如果他选择最优的门来解锁，牛群需要行走的最小总距离是多少。每头牛行走的距离是她经过的内部门的数量。

输入格式（文件 cbarn.in）：

第一行输入包含 $n$。接下来的 $n$ 行分别包含 $r_1$ 到 $r_n$。

输出格式（文件 cbarn.out）：

请输出牛群需要行走的最小总距离。

输入样例

5  
4  
7  
8  
6  
4

输出样例

48

hint

在此示例中，最佳的解法是让牛从需要 7 头牛的房间进入。