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
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N;
	cin >> N;
	vector<int> A(N);
	for(int& x : A){
		cin >> x;
	}
	vector<int> freq(N+1, 0);
	for(int x : A) freq[x]++;
	sort(freq.rbegin(), freq.rend());
	int cnt = 0;
	int used = 0;
	for(int f : freq){
		used++;
		cnt += f + (f-1);
		if(cnt >= N){
			break;
		}
	}
	cout << used << '\n';
}