Description

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

这个城堡是只有一层的，并且是一个环形的结构。在这个环形的结构里面存在着很多的房间，每个房间有不同的好玩的玩具。每个小朋友可以自己选择一个房间去玩，当前城堡的第 i 个房间有 ai 个小朋友在玩。

图 1: 样例里面城堡的 5 个房间
天快黑了，小朋友们打算回家了。小 A 和小 B 决定让所有的小朋友先到一个房间集合，然后大家一起回家去。这个环形的城堡中，相邻的 2 个房间之间都有一扇门可以走通。我们规定，一个小朋友走过一扇门的路程就是 1，小朋友只能在环形城堡中逆时针行走。现在，小 A 和小 B 很好奇，他们想要知道在哪个房间集合，所有小朋友的总路程可以最短。现在请你帮忙来解决这个问题，并输出最短的总路程。

Input Format

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

Output Format

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

5
4
7
8
6
4

48

Hint

【样例解释】

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

Source

模拟 前缀和