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
#include <bits/stdc++.h>
#define jd "DEBUG"
#define space " "
#define endl "\n"
#define PRINT(v) std::cout<<#v<<": "<<v<<endl;
#define PRINTV(v) std::cout<<#v<<": "; for(auto e : v)cout<<e<<" ";cout<<endl;
typedef long long ll;
typedef std::vector<int> vi;
using namespace std;

template <typename T = int>
T in(){
    T inx;
    cin>>inx;
    return inx;
}
bool comp(pair<int,int> a, pair<int,int> b){
    if(a.second < b.second)
        return true;
    
    return false;
}

vector<pair<int,int>> v;

int findLider(int start){
    for(int i = start+1; i < v.size(); i++){
        if(v[start].second < v[i].second*2)
            return i;
    }

    return -1;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n = in<>();
    map<int,int> m;
    for(int i = 0; i < n; i++){
        m[in<>()]++;
    }

    
    for(auto & [key, value] : m){
        v.push_back({key,value});
    }

    sort(v.begin(), v.end(), comp);

    int ans = 0;
    
    int full_size = 0;
    int big_size = 0;

    for(int i = 0; i < v.size(); i++){
        /*
            jezeli v[i].1 != -1 (nie uzyte) to:
                jeżeli mamy znalezionego lidera to:
                    sprawdzamy czy mozemy chlopa wlozyc
                    jak nie mozemy fuLL_size, big_size = 0, szukamy nowego lidera
                jeżeli nie mamy lidera to:
                    szukamy lidera

            pamietamy zeby ustawiac v[i].1 na -1 po uzyciu
        */

       if(v[i].first == -1)  // czy uzyte
        continue;

        if(big_size != 0){  // czy mozemy wsadzic juz
            if(full_size + v[i].second < big_size*2){ 
                v[i].first=-1;
                full_size+=v[i].second;
                continue;
            }
        }

        big_size=0;
        full_size=0;
        v[i].first=-1;
        ans++;

        int lider = findLider(i);
        if(lider==-1)
            continue;
        
        v[lider].first=-1;
        big_size = v[lider].second;
        full_size = big_size + v[i].second;
    }
    cout<<ans<<endl;
}