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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Mateusz Lambert
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <climits>
#include <algorithm>
#define ll long long
#define int128 __uint128_t
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define si set <int>
#define sl set <ll>
#define mins(x) *x.begin()
#define maxs(x) *x.rbegin()
#define vii vector <pair<int, int>>
#define vl vector <ll>
#define vll vector<pair<ll, ll>>
#define vb vector <bool>
#define vs vector <string>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sec second
#define fir first
using namespace std;


int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	
	int n;	cin >> n;
	vi occ(n+1, 0);
	for (int i=0; i<n; i++){
		int x; cin >> x;
		occ[x]++;
	}
	vi occs;
	for (int i=1; i<=n; i++) if (occ[i]) occs.pb(occ[i]);
	sort(all(occs), greater<int>());
	ll sum_all=0;
	int p=occs.size()-1, ans=0;
	for (int l=0; l<=p; l++){
		if (sum_all==n) break;
		sum_all += occs[l];
		int mx = occs[l]-1, sum=0;
		while (l<p && sum+occs[p]<=mx){
			sum += occs[p];
			sum_all += occs[p];
			p--;
		}
		occs[p] -= mx-sum;
		sum_all += mx-sum;
		ans++;
	}
	cout << ans << '\n';
}