作为当代建筑的爱好者，农夫约翰建造了一个完美圆环形状的新牛棚。
牛棚内部有 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
最佳方案是让奶牛们从第二个房间进入。