A. 圆形牛棚

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

作为当代建筑的爱好者,农夫约翰建造了一个完美圆环形状的新牛棚。

牛棚内部有 n 个房间,围成一个环形,按顺时针编号为 1∼n ,所有相邻房间之间的距离均为 1

每个房间都既有通向相邻两个房间的门,也有通向牛棚外部的门。

约翰想让第 i 个房间内恰好有 r_i 头牛。

为了让奶牛们有序的进入牛棚,他计划打开一个外门,让牛从该门进入。

然后,每头牛顺时针(即当 i<n 时,第 i 个房间只能走到第 i+1 个房间;当 i=n 时,第 i 个房间只能走到第 1 个房间)穿过房间,直到到达合适的房间为止。

约翰希望通过合理选择打开的门,使得所有奶牛的行走距离之和尽可能小(这里只考虑每头牛进入牛棚以后的行走距离)。

请确定他的奶牛需要行走的最小总距离。

输入格式

第一行包含整数 n。

接下来 n 行,包含 r_1, …, r_n

输出格式

输出所有奶牛需要行走的最小总距离。

样例

输入样例:

5
4
7
8
6
4

输出样例:

48

样例解释

最佳方案是让奶牛们从第2个房间进入。

数据范围与提示

3≤n≤1000,1≤r_i≤100