题目描述

小 A 有一个长度为 $n$ 的非负整数数组 $a = [a_1, a_2, \ldots, a_n]$。他会反复执行以下操作，直到数组中所有元素都变为 $0$。每次操作包含三个步骤：

1. 在数组中找到最大的元素，记其下标为 $k$；若有多个最大值，取下标最大的那个。
2. 在数组中所有不为 $0$ 的元素里找到最小的值 $a_j$。
3. 将 $a_k$ 减去 $a_j$。

例如，数组 $a = [2, 3, 4]$ 需要 $7$ 次操作才能全部变为 $0$：

$$[2, 3, 4] \rightarrow [2, 3, 2] \rightarrow [2, 1, 2] \rightarrow [2, 1, 1] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]$$

给定数组 $a$，请计算需要多少次操作才能使数组中所有元素都变为 $0$。可以证明这一过程必然在有限步内结束。

输入格式

第一行一个正整数 $n$，表示数组长度。
第二行 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。

输出格式

一行一个正整数，表示所需的操作次数。

样例

3
2 3 4

7

5
1 3 2 2 5

13

提示

对于所有测试点，保证 $1 \leq n \leq 100$，$0 \leq a_i \leq 100$。