嘉然小姐的糖果

伟大的主——圣嘉然大发慈悲地把甜蜜的糖果给了阴湿带病的鼠鼠们，鼠鼠们可高兴了，但很快它们发现每只鼠鼠分到的糖果的数量都不一样，作为团结的粉丝，它们决定让糖果多的鼠鼠把糖果分给糖果少的鼠鼠使每只鼠鼠都能拿到相同的糖果（圣嘉然发的糖果总数能保证鼠鼠们都能分到同样的糖果）。鼠鼠们没什么脑子，因此它们只会围成一个圈，把手上的糖果分一些给相邻的两只鼠鼠，不过他们每分一个糖果，武圣贝拉就会打嘉然一棍，虽然嘉然被打和鼠鼠们没什么关系，但鼠鼠们还是想知道然然最少会被打多少棍。

第一行输入一个正整数 n，表示鼠鼠的个数。

接下来 n 行，每行一个整数 a[i]，表示第 i 只鼠鼠初始得到的糖果的颗数。

1≤n≤1000000
0≤a[i]≤2×109

输出一个整数，表示然然最少会被打多少棍。

4
1 2 5 4

4