题目描述

有N个牛舍，围成一圈，按照顺时针方向依次编号为1〜N，相邻的牛舍之间都有连接通道，牛们只能按照顺时针方向通过这些通道。每间牛舍大小不一，容纳的牛的数量也不一，已知各牛舍容纳牛的数量。现在可以在某牛舍设置一个大门，所有的牛都只能从这个门进入，然后按顺时针方向走到其他牛舍。请设置这个大门，使得牛们入舍行走的距离最小。

输入格式

第1行，一个数N，为牛舍的数量。

第2行，N个整数，表示各牛舍容纳牛的数量。

输出格式

一个整数，表示牛入舍的最小距离。

输入样例#1

10
4 7 18 16 14 16 7 13 10 2

输出样例#1

354

题目说明

• $3 \leq N \leq 1000$
• 每间牛舍容纳的牛的数量不大于100