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

using namespace std;

const int N = 500 * 1000 + 1;
int occ[N];

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    
    int n, number;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> number;
        occ[number]++;
    }
    vector<int> reps;
    for (int i = 0; i < N; i++)
        if (occ[i] > 0)
            reps.push_back(occ[i]);
    sort(reps.begin(), reps.end());
    int seq = 0;
    int i = 0, j = reps.size() - 1;
    while (i <= j) {
        int sum = reps[j] - 1;
        while (i < j && reps[i] <= sum) {
            sum -= reps[i];
            reps[i++] = 0;
        }
        reps[i] -= sum;
        j--;
        seq++;
    }
 
    cout << seq << "\n";
    return 0;
}