Problem1938--击鼓传花

1938: 击鼓传花

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 128 MB

Submit

Description

岳麓山下旌旗卷,新月湖畔起歌声。湖南中医药大学运动会隆重开幕了,小 Q 所在的班级参加了“击鼓传花”趣味比赛。
比赛规则如下,所有队员围成一个圈,最开始每人手里拿着一些花束,但每个人所拿的数量不一定相同,队员需要传递花束,使得每个人的花束数量相同,第 i 个人的花束只能给第 i+1 或 i-1 个人(1 号可以给n 号,n 号也可以给 1 号)。 
每个鼓点只允许一个人传送一束花,最终要求每个人手里的花束数量相同,用时最少的班级获胜。 
小 Q 作为班长,他需要想出一个办法,使所用的总鼓点数尽可能少。聪明的你能告诉小 Q 最少需要花多少鼓点吗?

Input

单组数据
第一行 n,代表队员数量。
第 2 行到第 n+1 行,每行一个整数 a[i],代表每个队员已经拿到的花束。
1 ≤ n ≤ 106, 0 ≤ a[i] ≤ 2 × 109

Output

一个整数,代表最少需要的鼓点数。

Sample Input Copy

4
1
2
5
4

Sample Output Copy

4