糖果盒里有n颗糖果,第i颗糖的种类为ai(1≤ai≤n)。
明明的生日马上就要到了,为此你必须按照以下规则从这n颗糖果中挑选一些糖果作为一份生日礼物送给明明:礼物中每种糖果的数量应该是不同的。
例如,假如礼物中有两颗种类1的糖果和两颗种类2的糖果,则是不可行的。假如礼物中有两颗种类1的糖果和一颗种类2的糖果,则是可行的。
为了能够为明明准备生日礼物,相同种类的糖果可以不用全部放入礼盒中,也不是所有种类的糖果都需要放入礼盒中。
请问,礼盒中最多有多少颗糖果呢?
糖果盒里有n颗糖果,第i颗糖的种类为ai(1≤ai≤n)。
明明的生日马上就要到了,为此你必须按照以下规则从这n颗糖果中挑选一些糖果作为一份生日礼物送给明明:礼物中每种糖果的数量应该是不同的。
例如,假如礼物中有两颗种类1的糖果和两颗种类2的糖果,则是不可行的。假如礼物中有两颗种类1的糖果和一颗种类2的糖果,则是可行的。
为了能够为明明准备生日礼物,相同种类的糖果可以不用全部放入礼盒中,也不是所有种类的糖果都需要放入礼盒中。
请问,礼盒中最多有多少颗糖果呢?
每个测试样例2行:
第一行一个整数n (1≤n≤2e5):糖果的数量;
第二行共n个整数a1,a2,…,an(1≤ai≤n):ai为第i颗糖果的种类;
3 8 1 4 8 4 5 6 3 8 16 2 1 3 3 4 3 4 4 1 3 2 2 2 4 1 1 9 2 2 4 4 4 7 7 7 7
3 10 9
对于第1个测试样例,我们可以选择2颗种类8的糖果和1颗种类5的糖果放入礼盒中,没有比它更优的方案了。所以礼盒中最多有3颗糖果。
对于第2个测试样例,我们可以选择4颗种类4的糖果,3颗种类2的糖果,2颗种类3的糖果,1颗种类1的糖果,礼盒中最多有10颗糖果。