题目描述

小理最近犯上了强迫症，他总是想要把一个序列里的元素变得两两不同，而他每次可以执行一个这样的操作，他可以选择序列里的任意两个元素相加，不妨记作 $a_i$ 和 $a_j$，然后把 $a_i+a_j$ 放进序列里，再删掉 $a_i$ 和 $a_j$ 其中的随便一个，问最少操作多少次可以完成小理的愿望？

输入格式

输入共两行。

第一行一个整数 $n$，表示序列的长度。

第二行 $n$ 个整数 $a_i$ 表示序列的每个整数。

输出格式

输出一行表示答案。

样例输入输出

样例输入

3
1 2 2

样例输出

1

数据范围

对于 $100%$ 的数据，保证 $1 \le n \le 10^{5}$，$1 \le a_i < 10^{9}$。

样例解释

将序列的第 $1$ 个整数和序列的第 $2$ 个整数相加，再删掉第 $2$ 个整数。