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
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#ifndef DEBUG
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template<typename T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using usize = size_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128_t;
using u128 = __uint128_t;
istream& operator>>(istream& is, i128& x) { i64 x_; is >> x_; x = i128(x_); return is; }
istream& operator>>(istream& is, u128& x) { u64 x_; is >> x_; x = u128(x_); return is; }
ostream& operator<<(ostream& os, const u128& x) {
    constexpr u64 d19 = 10'000'000'000'000'000'000ULL;
    if (x > d19){ os << u64(x / d19) << setfill('0') << setw(19) << u64(x % d19); }
    else { os << u64(x); }
    return os;
}
ostream& operator<<(ostream& os, const i128& x) { 
    if (x >= 0) { os << u128(x); }
    else { os << '-' << u128(-x); }
    return os;
}
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i32 uid(i32 a, i32 b) { return uniform_int_distribution<i32>(a, b)(rng); }
i64 uld(i64 a, i64 b) { return uniform_int_distribution<i64>(a, b)(rng); }

#ifdef DEBUG
#include <debug.cpp>
#else
#define dbg(...) 43
#endif

const i64 INFLL = 1'000'000'000'000'000'005LL;
const i32 INF = 1'000'000'005;

i64 floor_div(i64 x, i64 y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x >= 0) return x / y;
	return (x + 1) / y - 1;
}

i64 ceil_div(i64 x, i64 y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x <= 0) return x / y;
	return (x - 1) / y + 1;
}

char nl = '\n';

void test_case(){
    i32 n; cin >> n;
    map<i32, i32> fq;
    for (i32 i = 0; i < n; i++){
        i32 x; cin >> x; fq[x]++;
    }
    vector<i32> v;
    for (auto [x, cnt] : fq){
        v.pb(cnt);
    }
    sort(all(v));
    n = v.size();
    i32 ans = 0;
    i32 p = 0;
    for (i32 i = n-1; p <= i; i--){
        ans++;
        i32 rem = v[i] - 1;
        while (p < i && v[p] <= rem){
            rem -= v[p++];
        }
    }
    cout << ans << nl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    i32 T = 1;
    while (T--){
        test_case();
    }
    return 0;
}