题目描述

小明非常喜欢吃美食，同时他非常讨厌吃到重复的东西.小云为小明准备了$n$道美食，其中第$i$道美食的特征值为$a_i$，因为小明讨厌重复的东西，所以小云想通过混合美食来改变其特征值使得所有美食特征值互不相同。具体的小云每次可以选择两个特征值分别为$x,y$的美食并将$x$加入$y$中变成特征值为$x$和$x+y$的美食，现在小云想知道他最少需要混合多少次使得所有美食特征值互不相同。

输入描述

第一行一个正整数$n$。 接下来一行$n$个数字分别表示每个美食的特征值。

对于所有的数据，$n \leq 100000$

保证$1 \leq a_i \leq n$。

输出描述

输出一个非负整数表示最小混合的次数

样例

输入

6
1 4 1 3 5 5

输出

2

提示

小云可以先将特征值为$5，1$的美食混合得到$5，6$。再将特征值为$6，5$的美食混合得到$6，11$，此时所有美食特征值分别为$1，4，6，3，5，11$，可以证明没有次数更少的方案。