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

using Counts = std::unordered_map< int, int >;

struct Cmp {
	Counts cnt;

	bool operator() (int const a, int const b) {
		if (cnt[a] != cnt[b]) { return cnt[a] > cnt[b]; }
		return a > b;
	}
};

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

	int n; std::cin >> n;
	std::vector< int > ciag;
	Counts zliczenia;

	ciag.resize(n);
	for (int i = 0; i < n; ++i) {
		std::cin >> ciag[i];
		zliczenia[ ciag[i] ] += 1;
	}

	std::sort(ciag.begin(), ciag.end(), Cmp{ zliczenia });

	int wynik = 0;

	int pocz = 0;
	int kon = n;

	while (pocz < kon) {
		wynik += 1;

		int curr = ciag[pocz];
		auto is_different = [curr](int const i) { return i != curr; };

		auto it = ciag.begin(); std::advance(it, pocz);
		auto et = ciag.begin(); std::advance(et, kon);

		auto nt = std::find_if(it, et, is_different);

		int odl = std::distance(it, nt);

		pocz += odl;
		kon -= (odl - 1);
	}

	std::cout << wynik << "\n";
	return 0;
}