#NC16301. 强迫症

强迫症

题目描述

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

输入格式

第一行一个整数 nn,表示序列的长度(1≤n≤1051\le n\le 10^5)。

第二行 nn 个整数 aia_i,表示序列的每个整数(1≤ai≤1091\le a_i\le 10^9)。

输出格式

输出一行表示答案

提示

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

样例 1

3
1 2 2
1

来源

牛客原题