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
36
37
38
39
40
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif



int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	cin >> n;
	vector<int> cnt(n);
	for(auto i = 0; i < n; ++ i){
		int x;
		cin >> x, -- x;
		++ cnt[x];
	}
	vector<int> order(n);
	iota(order.begin(), order.end(), 0);
	ranges::sort(order, [&](int x, int y){ return cnt[x] > cnt[y]; });
	for(auto i = 0, sum = 0, rem = n; i < n; ++ i){
		int x = order[i];
		rem -= cnt[x];
		sum += cnt[x] - 1;
		if(sum >= rem){
			cout << i + 1 << endl;
			return 0;
		}
	}
	assert(false);
	return 0;
}

/*

*/