张三有一个天平和 $n$ 种质量不同的砝码，第 $i$ 种砝码的质量为 $a_i$，每种砝码都有无数个。他想选出其中的若干种砝码，用以称量剩余的砝码。具体来说，张三会选出种类尽量少的砝码，设选出来的砝码集合为 $S$ ，则他希望对于所有剩下的砝码 $i$ ，他都可以先将一个 $i$ 类砝码放在天平左侧，再向天平的左侧、右侧分别放入任意个种类在 $S$ 内的砝码，使得天平平衡。请你告诉张三他至少要选多少个砝码。

对于 $30\%$ 的数据： $1 \le n \le10,1\le a_i \le 20$

对于 $100\%$ 的数据：$1 \le n \le 50,1 \le a_i \le 1e7$

样例1：

input

样例1
4
5 4 1 8
样例2
3
15 25 9

output

样例1
1
样例2
2

求思路QWQ