题目描述

小 A 有一个由 n 个非负整数构成的数组 a=[a₁,a₂,…,aₙ]。他会对数组 a 重复进行以下操作，直到数组 a 只包含 0。在一次操作中：

1. 在数组 a 中找到最大的整数，记其下标为 k。如果有多个最大值，选择下标最大的。
2. 从数组 a 所有不为零的整数中找到最小的整数 aⱼ。
3. 将 aₖ 减去 aⱼ。

例如，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]

输入格式

第一行一个正整数 n（1 ≤ n ≤ 100）
第二行 n 个非负整数 aᵢ（0 ≤ aᵢ ≤ 100）

输出格式

输出一个整数，表示将数组所有元素变为 0 的操作次数。

样例

样例1

输入

3
2 3 4

输出

7

样例2

输入

5
1 3 2 2 5

输出

13

数据范围

• 1 ≤ n ≤ 100
• 0 ≤ aᵢ ≤ 100