数组清零

题目描述

⼩ A 有⼀个由 个⾮负整数构成的数组 。他会对数组 重复进⾏以下操作，直到数组 只包含 。在⼀次操作中，⼩ A 会依次完成以下三个步骤：

1. 在数组 中找到最⼤的整数，记其下标为 。如果有多个最⼤值，那么选择其中下标最⼤的。
2. 从数组 所有不为零的整数中找到最⼩的整数 。
3. 将第⼀步找出的 减去 。 例如，数组 需要 次操作变成 ： ⼩ A 想知道，对于给定的数组 ，需要多少次操作才能使得 中的整数全部变成 。可以证明， 中整数必然可以在 有限次操作后全部变成 。你能帮他计算出答案吗？

输入格式

第⼀⾏，⼀个正整数 ，表⽰数组 的长度。 第⼆⾏， 个⾮负整数 ，表⽰数组 中的整数。

输出格式

⼀⾏，⼀个正整数，表⽰ 中整数全部变成 所需要的操作次数。

样例输入 #1

3
2 3 4

样例输出 #1

7

样例输入 #2

5
1 3 2 2 5

样例输出 #2

13

数据范围

对于所有测试点，保证 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 3级，难度等级：⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。