题目描述

小 A 有一个由$n$个非负整数构成的数组$a=[a_1,a_2,...,a_n]$。他会对数组$n$重复进行以下操作，直到数组 只包含0。在一次操作中，小 A 会依次完成以下三个步骤：

1. 在数组$a$中找到最大的整数，记其下标为$k$。如果有多个最大值，那么选择其中下标最大的。
2. 从数组$a$所有不为零的整数中找到最小的整数$a_j$。
3. 将第一步找出的$a_k$减去$a_j$。

例如，数组$a=[2,3,4]$需要$7$次操作变成$[0,0,0]$： $[2,3,4]⇥[2,3,2]⇥[2,1,2]⇥[2,1,1]⇥[1,1,1]$ $⇥[1,1,0]⇥[1,0,0]⇥[0,0,0]$ 小 A 想知道，对于给定的数组$a$，需要多少次操作才能使得$a$中的整数全部变成$0$。可以证明，$a$中整数必然可以在有限次操作后全部变成$0$。你能帮他计算出答案吗？

输入格式

第一行，一个正整数$n$，表示数组$a$的长度。 第二行，$n$个非负整数$a_1,a2,...,a_n$，表示数组$a$中的整数。

输出格式

一行，一个正整数，表示 $a$ 中整数全部变成 $0$ 所需要的操作次数。

样例 #1

样例输入 #1

3
2 3 4

样例输出 #1

7

样例 #2

样例输入 #2

5
1 3 2 2 5

样例输出 #2

13

提示

数据范围 对于所有测试点，保证$1 \leq n \leq 100$，$0 \leq a_i \leq 100$