圆形牛棚

题目描述:

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

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

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

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

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

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

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

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

输入格式:

第一行包含整数 n。

接下来 n 行，包含 r₁, … , r_n。

输出格式:

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

数据范围:

3 ≤ n ≤ 1000 ,
1 ≤ ri ≤ 100

样例输入:

5
4
7
8
6
4

样例输出:

48

提示:

样例解释

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

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2016 February Contest Bronze