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

constexpr int MAXN = 500001;

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int prev = a[0];
    int cnt = 0;
    vector<int> cnts;
    for (int v : a) {
        if (v == prev) {
            cnt++;
        } else {
            cnts.push_back(cnt);
            cnt = 1;
            prev = v;
        }
    }
    cnts.push_back(cnt);
    sort(cnts.begin(), cnts.end());
    int res = 0;
    int j = size(cnts) - 1;
    int i = 0;
    while (i <= j) {
        if (!cnts[j]) break;
        res++;
        int rem = cnts[j] - 1;
        while (i < j && rem) {
            int diff = min(rem, cnts[i]);
            if (diff) {
                rem -= diff;
                cnts[i] -= diff;
            }
            if (!cnts[i]) i++;
        }
        j--;
    }
    cout << res << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

// #ifdef LOCAL
//     int t; cin >> t; while (t--)
// #endif

    solve();

    cout.flush();
}