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
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int solve(int n, vector<int>& cnt)
{
	sort(cnt.begin(), cnt.end());

	int cur = n;
	int res = 0;

	while (n > 0)
	{
		n -= cnt[cur--] * 2 - 1;
		++res;
	}

	return res;
}

int main()
{
	int n, a;
	cin >> n;

	vector<int> cnt(n + 1);

	for (int i = 0; i < n; ++i)
	{
		cin >> a;
		++cnt[a];
	}

	int res = solve(n, cnt);

	cout << res << endl;

	return 0;
}