题目描述

教室里有 $n$ 位同学，每位同学都有若干个苹果，第 $i$ 位同学拥有 $a_i$ 个苹果。 翁老师带来了满满的一箱苹果（假设有无数个），他今天的目标是给一些同学若干个苹果，使得这 $n$ 位同学拥有的苹果的数量都相同。 但是苹果吃多了肚子也不舒服，所以翁老师希望在满足 每位同学拥有的苹果数量都相同 前提下，分给这 $n$ 位同学的苹果总数尽可能地少。

问：翁老师至少需要分给 $n$ 位同学的苹果总数是多少？

注：

• 翁只能分出去苹果，而不能抢夺同学们手中的苹果；
• 本题假设全程没有同学偷偷把自己的苹果吃掉；
• 本题假设翁老师拥有的苹果是无限多的；
• 翁老师分出去的苹果都是整数个。

输入格式

输入的第一行包含一个整数 $n$，表示同学人数。

输入的第二行包含 $n$ 个整数，两两之间以一个空格分隔，其中第 $i$ 个整数表示第 $i$ 位同学初始时拥有的苹果的数量。

输出格式

一个整数，表示翁老师至少需要分给 $n$ 为同学的苹果总数。

5
0 1 2 3 4

10

5
1 2 1 2 1

3

5
6 6 6 6 6

0

提示

样例 1 解释

翁老师分给第 $1$ 位同学 $4$ 个苹果，第 $2$ 位同学 $3$ 个苹果，第 $3$ 位同学 $2$ 个苹果，第 $4$ 位同学 $1$ 个苹果，第 $5$ 位同学 $0$ 个苹果，则每位同学都将拥有 $4$ 个苹果。翁老师一共分出了 $4+3+2+1+0=10$ 个苹果。

数据范围

• 对于 $50\%$ 的数据 $1 \le n \le 100, 0 \le a_i \le 10^2$。

• 对于 $100\%$ 的数据 $1 \le n \le 10^5, 0 \le a_i \le 10^9$。