圆形牛棚

题目描述

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

牛棚内部有 $n$ 个房间，围成一个环形，按顺时针编号为 $1\sim 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

提示

#### 数据范围 $3\le n\le 1000,1\le r_{i}\le 100$

样例解释

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

来源

童程童美