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

int main() {
	int n;
	std::cin >> n;
	
	std::vector<int> input(n);
	for (int i = 0; i < n; ++i) {
		int x;
		std::cin >> x;
		input[i] = x;
	}
	std::sort(input.begin(), input.end());
	input.push_back(-1);
	
	std::map<int, int> counts;
	
//	std::cout << "input:";
//	for (int x : input) {
//		std::cout << ' ' << x;
//	}
//	std::cout << '\n';
	
	int prev = input[0];
	int cnt = 1;
	for (int i = 1; i <= n; ++i) {
		if (input[i] == prev) {
			++cnt;
		} else {
//			std::cout << "counts[prev="<<prev<<"] = cnt="<<cnt<<"\n";
			counts[prev] = cnt;
			prev = input[i];
			cnt = 1;
		}
	}
	
	// [cnt, num]
	std::set<std::pair<int, int>> set;
	for (const auto &[x, c] : counts) {
		set.emplace(c, x);
	}
	
//	std::cout << "set:";
//	for (auto [c, x] : set) {
//		std::cout << " (" << c << "," << x << ")";
//	}
//	std::cout << '\n';
	
	int answer = 0;
	while (!set.empty()) {
		auto [hi_cnt, hi_num] = *std::prev(set.end());
		set.erase(std::prev(set.end()));
		int left = hi_cnt - 1;
//		std::cout << "hi_cnt, hi_num = "<<hi_cnt<<", "<<hi_num<<"\n";
		while (left > 0 && !set.empty()) {
			auto [lo_cnt, lo_num] = *set.begin();
//			std::cout << "  left="<<left<<"; lo_cnt, lo_num = "<<lo_cnt<<", "<<lo_num<<"\n";
			if (left >= lo_cnt) {
				left -= lo_cnt;
				set.erase(set.begin());
			} else {
				set.erase(set.begin());
				set.emplace(lo_cnt - left, lo_num);
				left = 0;
			}
		}
		++answer;
	}
	
	std::cout << answer << '\n';
}