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
#include <stdio.h>
#include <stdlib.h>

static int compare_int(const void *pa, const void *pb)
{
	return *((int *) pa) - *((int *) pb);
}

int n, c[500001], r, i;

int main(void)
{
	scanf("%u", &n);
	for (i = 0; i < n; i++) {
		unsigned x;

		scanf("%u", &x);
		c[x]++;
	}

	qsort(&c[1], n, sizeof(c[1]), compare_int);

	for (i = n; i > 0 && n > 0; i--)
		if (c[i]) {
			r++;
			n -= 2 * c[i] - 1;
		}

	printf("%u\n", r);
	return 0;
}