1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;

int n, in, tab[500000], s, res;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 0; i < n; i++) {
        cin>>in;
        tab[in - 1]++;
    }
    sort(tab, tab + n);
    for(int i = n - 1; s < n; i--) {
        s += (2*tab[i] - 1);
        res++;
    }
    cout<<res;
}