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

int INT() {
	int in; scanf("%d", &in);
	return in;
}

int main() {
	int n=INT();
	vector <int> a(n+1, 0), amount(n+1, 0);
	for(int i=0; i<n; ++i) ++a[INT()];
	for(int &x : a) if(x) ++amount[x];

	deque <int> dq;
	for(int i=1; i<=n; ++i) while(amount[i]) dq.push_back(i), --amount[i];

	int ans=0;
	while(!dq.empty()) {
		++ans;
		int to_pair=dq.back()-1;
		dq.pop_back();
		while(to_pair && !dq.empty()) {
			int x=dq.front();
			dq.pop_front();
			if(x<=to_pair) to_pair-=x;
			else dq.push_front(x-to_pair), to_pair=0;
		}
	}
	printf("%d\n", ans);
	exit(0);
}