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
// LID: Liderzy [B] | 2024-03-11 | Solution by dkgl
// https://sio2.mimuw.edu.pl/c/pa-2024-1/p/lid/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  deque<int> value_count(n);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    --x;
    ++value_count[x];
  }
  sort(value_count.begin(), value_count.end());
  int result = 0;
  while (!value_count.empty() && value_count.back() != 0) {
    ++result;
    int to_remove = value_count.back() - 1;
    value_count.pop_back();
    while (to_remove > 0 && !value_count.empty()) {
      int removed = min(value_count.front(), to_remove);
      to_remove -= removed;
      if (removed == value_count.front()) value_count.pop_front();
      else value_count.front() -= removed;
    }
  }

  cout << result << endl;
  return 0;
}