题目描述

薯条哥非常喜欢吃美食，同时他非常讨厌吃到重复的东西.

鸭哥为薯条哥准备了$n$道美食，其中第$i$道美食的特征值为$a_i(1\le a_i\le n)$，

因为薯条哥讨厌重复的东西，所以鸭哥想通过混合美食来改变其特征值使得所有美食特征值互不相同。

具体的鸭哥每次可以选择两个特征值分别为$x,y$的美食并将$x$加入$y$中变成特征值为$x$和$x+y$的美食，

现在鸭哥想知道他最少需要混合多少次使得所有美食特征值互不相同。

输入描述

第一行输入一个正整数$n(1\le n\le 10^5)$。

接下来一行输入$n$个数字分别表示每个美食的特征值$a_i(1\le a_i\le n)$。

输出描述

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

样例

输入

6
1 4 1 3 5 5

输出

2

样例解释

薯条哥可以先将特征值为$5,1$的美食混合得到$5,6$。

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