有n个小朋友坐成一圈，每人手上有若干块饼干。老师要求他们进行传递，使得每个人手上的饼干数量相同。
每个小朋友只能传递饼干给左右相邻的小朋友，保证饼干总量是n的整数倍，问最少传递多少块饼干可以满足老师的要求。

多组输入。
每组数据第一行输入一个正整数n(n<=1e6)，第二行输入n个正整数，按顺时针给出每个小朋友持有的饼干数。

对于每组数据，输出被传递饼干数量的最小值，答案保证在64位整数范围内。

困难