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

int main() {
	int n;
	std::cin >> n;

	std::map<int, int> counter;
	for(int i = 0; i < n; ++i) {
		int x;
		std::cin >> x;
		++counter[x];
	}

	std::vector<std::pair<int, int>> counted;
	for(auto &[value, count] : counter)
		counted.emplace_back(value, count);

	std::vector<int> prefix(counted.size());
	for(unsigned i = 0; i < counted.size(); ++i)
		prefix[i] = counted[i].second;

	std::ranges::sort(counted, std::less(), [](auto const &p) { return p.second; });
	std::partial_sum(prefix.begin(), prefix.end(), prefix.begin());

	int result = 1;
	int removed = 0;
	while(counted.size()) {
		auto [value, count] = counted.back();
		counted.pop_back();

		if(count * 2 > n - std::min(removed, prefix[counted.size()]))
			break;

		n -= count;
		removed += count - 1;
		result += 1;
	}

	std::cout << result << '\n';
}