1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int n;
int t[500009];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    vector<int> cnt(n);
    for(int i=0;i<n;i++){
        cin>>t[i];
        cnt[t[i]]++;
    }
    sort(cnt.begin(),cnt.end());
    int s = 0;
    int w = 0;
    for(int i=n-1;i>=0;i--){
        s += 2*cnt[i]-1;
        w++;
        if(s>=n){
            cout<<w;
            return 0;
        }
    }
}