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
#include "bits/stdc++.h"
 
using namespace std;

template<typename _T> void _debug(const char *s, _T x){ cerr << s << " = " << x << "\n";}
template<typename _T, typename... R> void _debug(const char *s, _T x, R... r){ while(*s != ',') cerr << *s++; cerr << " = " << x << ", "; _debug(s + 1, r...);}
 
#define debug(...)  _debug(#__VA_ARGS__,  __VA_ARGS__)
 
#define sz(s)   int32_t(s.size())
#define all(x)  begin(x), end(x)
#define getuniqe(x) x.erase(unique(all(x)), end(x))
#define X first
#define Y second
 
using ll = long long;
using ld = long double;

#define int ll

const int N = 5e5 + 5;

int ile[N];

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;  cin >> n;
    vector<int> tab(n);
    for (int i = 0; i < n; i++) {
        cin >> tab[i];
        ile[tab[i]]++;
    }
    sort(all(tab)); getuniqe(tab);
    sort(all(tab), [&](int a, int b) {
        return ile[a] < ile[b];
        // return ile[a] < ile[b] || (ile[a] == ile[b] && a < b);
    });
    // for (int t: tab) cout << t << " ";
    int res = 0, ileL = 0, ileR = 0, l = 0, r = tab.size() - 1;
    while (l < r) {
        ileL = 0, ileR = ile[tab[r]], ile[tab[r]] = 0;
        while (l < r && ileL + ile[tab[l]] < ileR)
            ileL += ile[tab[l++]];
        if (l < r && ileL + ile[tab[l]] >= ileR) {
            ile[tab[l]] -= (ileR - 1) - ileL;
        }
        // debug(l, r, ileL, ileR);
        r--; res++;
    }
    if (l == r && ile[tab[l]] > 0) res++;
    cout << res << "\n";
    
}