1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#include<algorithm>
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,a[500009],b[500009];
main()
{
	read(n);for(int i=n,x;i--;read(x),++a[x]);
	sort(a,a+n);reverse(a,a+n);
	for(;a[m];++m);
	for(int i=0;i<m;b[i]=a[i]+(i?b[i-1]:0),++i);
	for(int i=0;i<m;++i)if(b[i]-i-1>=b[m-1]-b[i])
		{printf("%d",i+1);return 0;}
}