‹ 上一题下一题 ›

j01262. 环形糖果传递未做

1000 ms 256 MB 测试点 10 5级·贪心经典模型贪心贪心与排序/堆的配合

文件读写输入j01262.in输出j01262.out

题目描述

$n$ 个小朋友围成一圈，第 $i$ 人有 $c_{i}$ 颗糖果。每次传递：某人把一颗糖果交给相邻的人。已知糖果总数是 $n$ 的倍数，求最少多少次传递能使每人糖果数相等。

输入格式

第一行一个整数 $n$ ；第二行 $n$ 个整数 $c_{i}$ 。

输出格式

一行一个整数：最少传递次数。

样例

输入

4
1 2 5 4

输出

数据范围

$1 \leq n \leq 5 \times 1 0^{5}$ ， $0 \leq c_{i} \leq 1 0^{9}$ ；保证 $n$ 整除糖果总数

输入

输出

答案