题目描述

n人沿圆环坐好，每次可以把一颗糖传给任一相邻的人，代价1；糖果不可丢弃。求所有人糖数相等的最小总代价。

本题为一本通1432的本地训练修订版。

输入

第一行n，1≤n≤10^6；接下来n个整数ai，0≤ai≤10^6。保证总和能被n整除。

输出

一行最小代价，使用64位整数。

输入样例

4
1
2
5
4

输出样例

4

修订说明

补全糖果非负上界、总和可整除和64位答案。