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
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
    int n;
    std::cin >> n;

    std::unordered_map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int ai;
        std::cin >> ai;
        counts[ai] += 1;
    }

    std::vector<std::pair<int, int>> rev_counts;
    rev_counts.reserve(counts.size());
    for (auto p: counts) {
        rev_counts.emplace_back(p.second, p.first);
    }
    std::sort(rev_counts.begin(), rev_counts.end());

    int front = 0;
    int back = rev_counts.size() - 1;
    int filled = rev_counts[back].first - 1;
    for (;;) {
        if (front == back) {
            break;
        } else if (rev_counts[front].first <= filled) {
            filled -= rev_counts[front].first;
            front += 1;
        } else {
            back -= 1;
            filled += rev_counts[back].first - 1;
        }
    }
    std::cout << rev_counts.size() - back << "\n";
}