1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int ile[500001];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int i;
	int n;
	cin>>n;
	for (i = 0; i < n; i++){
		int x;
		cin>>x;
		ile[x]++;
	}
	vector<pair<int,int> > tab;
	for (i = 0; i <= 500000; i++){
		if (ile[i]){
			tab.push_back({ile[i],i});
		}
	}
	sort(tab.begin(),tab.end());
	reverse(tab.begin(),tab.end());
	int suma = 0;
	for (i = 0; i < (int)tab.size(); i++){
		auto j = tab[i];
		suma += j.first;
		if (suma-(i+1) >= n-suma){
			cout<<i+1<<"\n";
			return 0;
		}
	}
	return 0;
}