作为一名当代建筑学的爱好者，Farmer John已经建立了一个新的完美的圆形的牛棚。在这个牛棚里，这个圆形牛棚包含着一连串的n个房间，以1..n的编号在牛棚的周围顺势针排列着(3<=n<=1000)。每个房间有通向它两个相邻的门，并且有一个通向牛棚外的门。为了防止奶牛们乱跑，通向牛棚外的门一般都是锁着的。
Farmer John想要刚好Ai头奶牛呆在房间i中(1<=Ai<=100)，为了有序地把奶牛赶到牛棚里，他计划打开一间房的外门，这样奶牛就可以从那扇门进去了。然后每只奶牛顺时针方向穿过房间，直到到达合适的目的地。Farmer John想要知道不锁上哪扇门，可以使得所有的奶牛到达目的地的总步数最小。每头奶牛走的步数定义为她所穿过的在牛棚里面的房间。
第一行一个整数n表示圆形牛棚有n间房间。
接下来n行，每行一个整数表示a[1]..a[n]每个房间需要奶牛的数量。
5
4
7
8
6
448