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
71
72
73
74
75
76
77
78
// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    // Write C++ code here
    int n;
    cin >> n;
    unordered_map<int, int> map;
    
    for(int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        map[tmp]++;
    }
    
    vector<int> counts;
    for(auto& pair : map) {
        counts.push_back(pair.second);
    }
    
    sort(counts.begin(), counts.end());
    
    if(counts.size() == 1) {
        cout << 1 << endl;
        return 0;
    }
    
    int answer = 0;
    
    int start = 0, end = counts.size() - 1;
    
    while(start < end) {
        int big = counts[end];
        int small_sum = 0;
        
        if(counts[start] < big) {
            int poczatek = start;
            int koniec = start;
            int small_sum = counts[poczatek];
            
            for(int i = poczatek + 1; i < end; i++) {
                if(small_sum + counts[i] < big) {
                    small_sum += counts[i];
                    koniec = i;
                } else {
                    break;
                }
            }
            
            if(koniec + 1 < end) {
                int mozna_odjac = big - small_sum - 1;
                counts[koniec + 1] -= mozna_odjac;
            }
            
            start = koniec + 1;
            end--;
            answer++;
            
        } else {
	    int mozna_odjac = big - 1;
	   counts[start] -= mozna_odjac;	

            end--;
            answer++;
        }
        
    }
    
    if(start == end) answer++;
    
    cout << answer << endl;
    return 0;
}