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
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>

using namespace std;

const int MAX_V = 500000;
int value_to_quantity[MAX_V + 1];  // jak czesto wystepuje dana wartosc
int quantity_to_count[MAX_V + 1];  // jak czesto wystepuje dana czestosc

vector<int> bucket_sort_quantities() {
    for (int q: value_to_quantity) {
        quantity_to_count[q]++;
    }
    vector<int> quantities;
    for (int q = 1; q <= MAX_V; ++q) {
        int count = quantity_to_count[q];
        while (count--) {
            quantities.push_back(q);
        }
    }
    return quantities;
}

int main() {
    ios_base::sync_with_stdio(0);

    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        int v; cin >> v;
        value_to_quantity[v]++;
    }

    vector<int> quantities = bucket_sort_quantities();

    // cout << "quantities: ";
    // for (int q: quantities) {
    //     cout << q << ", ";
    // }
    // cout << endl;

    auto big_index = quantities.size() - 1;
    decltype(big_index) small_index = 0;

    int group_count = 1;
    int allowed_sum = quantities[big_index] - 1;
    int small_sum = 0;
    while (big_index > small_index) {
        while (big_index > small_index) {
            if (small_sum + quantities[small_index] <= allowed_sum) {
                small_sum += quantities[small_index];
                small_index++;
            } else {
                int xxx = allowed_sum - small_sum;
                quantities[small_index] -= xxx;
                break;
            }
        }
        if (big_index > small_index) {
            big_index--;
            group_count++;
            allowed_sum = quantities[big_index] - 1;
            small_sum = 0;
        }
    }

    cout << group_count << endl;


    return 0;
}