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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

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

inline int solve(){
//     for (int tst = 0; tst < 1000; ++tst){
//          ifstream cin(to_string(tst) + ".in");
          int n; cin >> n;
          map <int, int> cnt;
          for (int i = 0; i < n; ++i){
               int a; cin >> a;
               ++cnt[a];
          }
          vec <int> ss;
          for (auto &[x, k]: cnt){
               ss.push_back(k);
          }
          sort(rall(ss));
          int z = sz(ss);
          int ans = sz(ss) + 1;
          for (int l = 19; ~l; --l){
               ans -= 1 << l;
               if (ans <= 1){
                    ans += 1 << l;
                    continue;
               }
               int pt = ans;
               vec <int> tt = ss;
               for (int i = 0; i < ans; ++i){
                    int can = tt[i] - 1;
                    while(can > 0 && pt < z){
                         if (tt[pt] > can){
                              tt[pt] -= can;
                              break;
                         }
                         can -= tt[pt++];
                    }
               }
               if (pt != z){
                    ans += 1 << l;
               }
          }
          cout << ans;
//          ifstream checker(to_string(tst) + ".out");
//          int _ans;
//          checker >> _ans;
//          if (ans != _ans){
//               cout << "FUCK: " << ans << " " << _ans << "\n";
//               return 0;
//          }
//          cout << "done " << tst << "\n";
//     }
     return 0;
}

inline void precalc(){}

signed main(){
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     int tst = 1; //cin >> tst;
     precalc();
     while(tst--) solve();
     return 0;
}