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
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

constexpr uint32_t MAX_SIZE=500000;

struct num_chain
{
	uint32_t num = 0;
	std::map<uint32_t,uint32_t> nums;
};

void load(std::istream& in, num_chain& n)
{
	in >> n.num;
	for (int i =0; i < n.num; ++i)
	{
		uint32_t value = 0;
		in >> value;
		n.nums[value] ++;
	}
}

void print_map(std::ostream& out, num_chain const &n)
{
	out << "num: " << n.num << "\n";
	if (n.num < 10)
	{
		for (auto it = n.nums.begin(); it != n.nums.end(); it++)
		{
			out << "nums[" << it->first << "] = " << it->second << "\n";
		}
	}
}

void print_vect(std::ostream& out, std::vector<std::pair<uint32_t, uint32_t>> const &v)
{
	if (v.size() > 10)
	{
		return;
	}
	uint32_t i = 0;
	for (auto it = v.begin(); it != v.end(); it++)
	{
		out << "vect[" << i <<"] = " << it->first << ":" << it->second << "\n"; 
		i++;
	}
}

bool cmp(std::pair<uint32_t, uint32_t> &lhs, std::pair<uint32_t, uint32_t> &rhs)
{
	return lhs.second > rhs.second;
}
bool cmp2(std::pair<uint32_t, uint32_t> &lhs, std::pair<uint32_t, uint32_t> &rhs)
{
	return lhs.second <= rhs.second;
}

void sort_chains(std::map<uint32_t, uint32_t> &m, std::vector<std::pair<uint32_t,uint32_t>> &v)
{
	v.reserve(m.size());
	for (auto it = m.begin(); it != m.end(); it++)
	{
		v.push_back(*it);
	}
	sort(v.begin(), v.end(), cmp);
}

void pick_most_frequent(std::vector<std::pair<uint32_t, uint32_t>> &v,
		std::vector<std::pair<uint32_t,uint32_t>>::iterator &lider,
		std::vector<std::pair<uint32_t,uint32_t>>::iterator &additional)
{
	auto above_half = lider->second;
	uint32_t required_less_freq = above_half - 1;
	if (above_half >= 1 && lider != additional) 
	{
		while (required_less_freq > 0 && additional != lider) {
			if (additional->second > required_less_freq)
			{
				additional->second -= required_less_freq;
				required_less_freq = 0;
			}
			else 
			{
				required_less_freq -= additional->second;
				additional->second = 0;
				--additional;
			}
		}
	}
	lider ++;
}

void prog_main(std::istream& in, std::ostream& out)
{
	num_chain n;
	load(in, n);
	std::vector<std::pair<uint32_t, uint32_t>> v;
	sort_chains(n.nums, v);
	uint32_t num = 0;
	auto lider = v.begin();
	auto additional = v.end();
	while (lider != v.end() && lider->second != 0)
	{
	//	print_vect(std::cerr, v);
		pick_most_frequent(v, lider, additional);
		num++;
	}
	out << num << std::endl;
	//print_vect(std::cerr, v);
}



#ifndef TEST
int main(int argc, char* argv[])
{
	prog_main(std::cin, std::cout);
	return 0;
}
#endif