#P1016. 禾木分核桃

禾木分核桃

题目描述

教室里有 n(1n100)n(1 \le n \le 100) 位同学,每位同学都有若干颗核桃,第 ii 位同学拥有 ai(0ai100)a_i(0 \le a_i \le 100) 颗核桃。
禾木带来了满满的一箱核桃,他今天的目标是分给一些同学核桃,使得这 nn 位同学拥有的核桃的数量都相同。
但是核桃吃多了会长胖,所以禾木希望在满足 每位同学拥有的核桃数量都相同 前提下,分给这 nn 位同学的核桃总数尽可能地少。
问:禾木至少需要分给 nn 位同学的核桃总数是多少?

注:

  • 禾木只能分出去核桃,而不能抢夺同学们手中的核桃;
  • 本题假设全程没有同学偷偷把自己的核桃吃掉;
  • 本题假设禾木拥有的核桃是可以保证每位同学拥有相同数量的核桃的(足够多);
  • 禾木分出去的核桃都是整数个(没有破损的核桃)。

输入格式

输入的第一行包含一个整数 n(1n100)n(1 \le n \le 100),表示同学人数。
输入的第二行包含 nn 个整数,两两之间以一个空格分隔,其中第 ii 个整数表示第 ii 位同学初始时拥有的核桃的数量(0ai1000 \le a_i \le 100)。

输出格式

一个整数,表示禾木至少需要分给 nn 为同学的核桃总数。

样例

5
0 1 2 3 4
10
5
1 2 1 2 1
3
5
6 6 6 6 6
0

样例解释

  • 样例1中,禾木需要分给第 11 位同学 44 个核桃,第 22 位同学 33 个核桃,第 33 位同学 22 个核桃,第 44 位同学 11 个核桃,第 55 位同学 00 个核桃,则每位同学都将拥有 44 个核桃。禾木一共分出了 4+3+2+1+0=104+3+2+1+0=10 个核桃。
  • 样例2中,禾木需要分给第 113355 位同学各 11 个核桃,这样能保证每位同学都拥有 22 个核桃。禾木一共分出了 1+0+1+0+1=31+0+1+0+1=3 个核桃。
  • 样例3中,因为一开始每位同学就都拥有相同数量的核桃,所以禾木不需要分任何核桃。

数据范围

对于 100%100\% 的数据 1n100,0ai1001 \le n \le 100, 0 \le a_i \le 100