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
/* 2024
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

const int MAX_LENGTH = 500001;
int length;
int value;
int seq[MAX_LENGTH];
int sl;
int count[MAX_LENGTH];

int main(void)
{
    scanf("%d", &length);
    for(int l = 0; l < length; ++l)
    {
        scanf("%d", &value);
        if(!count[value]++)
            seq[sl++] = value;
    }

    std::sort(seq, seq + sl, [&](const int a, const int b)
        { return count[a] > count[b]; });

    int result = 0;
    for(int s = 0; s < sl && length > 0; ++s)
    {
        ++result;
        length -= count[seq[s]] * 2 - 1;
    }

    printf("%d\n", result);
    return 0;
}