Background

由于备战复试的过程中每天都要做很多的题目，小 $A$ 和小 $B$ 想去放松一下。于是，他们走了很多好朋友一起去一个城堡玩。

这个城堡是只有一层的，并且是一个环形的结构。在这个环形的结构里面存在着很多的房间，每个房间有不同的好玩的玩具。

每个小朋友可以自己选择一个房间去玩，当前城堡的第 $i$ 个房间有 $a_i$ 个小朋友在玩。天快黑了，小朋友们打算回家了。小 $A$ 和小 $B$ 决定让所有的小朋友先到一个房间集合，然后大家一起回家去。这个环形的城堡中，相邻的 $2$ 个房间之间都有一扇门可以走通。我们规定，一个小朋友走过一扇门的路程就是 $1$，同时规定小朋友只能按照逆时针的方向去走。

现在，小 $A$ 和小 $B$ 很好奇，他们想要知道在哪个房间集合，所有小朋友的总路程可以最短。现在请你帮忙来解决这个问题，并输出最短的总路程。

Input

输入的第一行是一个正整数 $N$，表示房间的总数。

接下来 $N$ 行，每行一个正整数，表示每个房间里面小朋友的数量 $a_i$，按照顺时针的方向输入。因为是环形的，所以显然房间 $1$ 和房间 $N$ 是首尾相接的。

Output

输出只有一行一个整数，表示让所有小朋友集合在一个房间的最小总路程。

Samples

5
4
7
8
6
4

48

Limitation

样例中 $5$ 个房间，每个房间的小朋友人数分别是 $4，7，8，6，4$。如果所有的小朋友都到第 $2$ 房间集合（即有 $7$ 个小朋友的房间），那么他们要走的总路程是最短的，是 $48$。

对于所有的数据：$1 ≤ N ≤ 10^5 , 1 ≤ a_i ≤ 10^6$。

对于数据编号

$1∼3$ 有 $N ≤ 10^3 , a_i ≤ 10^3$ , 所有的 $a_i$ 都是相同的

$4∼7$ 有 $N ≤ 10^3 , a_i ≤ 10^3$

$8∼10$ 有 $N ≤ 10^5 , ai ≤ 10^6$