题目描述
由于备战复试的过程中每天都要做很多的题目，小A 和小B 想去放松一下。于是，他们走了很多好朋友一起去一个城堡玩。
这个城堡是只有一层的，并且是一个环形的结构。在这个环形的结构里面存在着很多的房间，每个房间有不同的好玩的玩具。每个小朋友可以自己选择一个房间去玩，当前城堡的第i 个房间有ai 个小朋友在玩。
天快黑了，小朋友们打算回家了。小A 和小B 决定让所有的小朋友先到一个房间集合，然后大家一起回家去。这个环形的城堡中，相邻的2 个房间之间都有一扇门可以走通。我们规定，一个小朋友走过一扇门的路程就是1，同时规定小朋友只能按照顺时针的方向去走。现在，小A 和小B 很好奇，他们想要知道在哪个房间集合，所有小朋友的总路程可以最短。现在请你帮忙来解决这个问题，并输出最短的总路程。
输入
输入的第一行是一个正整数N，表示房间的总数。
接下来N 行，每行一个正整数，表示每个房间里面小朋友的数量ai，按照顺时针的方向输入。因为是环形的，所以显然房间1 和房间N 是首尾相接的。
输出
输出只有一行一个整数，表示让所有小朋友集合在一个房间的最小总路程。
样例输入输出
提示
样例中5 个房间，每个房间的小朋友人数分别是4，7，8，6，4。如果所有的小朋友都到第2 房间集合（即有7 个小朋友的房间），那么他们要走的总路程是最短的，是48。
【数据范围】
对于所有的数据：$ 1 \le N \le 10^5, 1 \le a_i ≤ 10^6$。
数据编号|数据范围|特殊性质
--|--|--
1-3 | $N \le 10^3, a_i \le 10^3$ |所有的ai 都是相同的
4-7 | $N \le 10^3, a_i \le 10^3$ |无
8-10| $N \le 10^5, a_i \le 10^6$| 无