题目描述

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

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

输入

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

输出

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

输入样例

4
1
2
5
4

输出样例

4

修订说明

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

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：补全糖果非负上界、总和可整除和64位答案。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1432。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。