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
#include <bits/stdc++.h>

using namespace std;

struct abc{
    int a=0,b=0,c=0;
};
bool comp(abc a, abc b){
    return a.a<b.a;
}
abc ile[500001];
int main()
{
    ios_base::sync_with_stdio(false);
    //for(int i=1;i<10000;++i)cout<<i<<' ';
    int n,a,roz=0;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a;
        if(ile[a].a==0)roz++;
        ile[a].a++;
        ile[a].b++;
    }
    sort(ile,ile+n+1,comp);
    int wczes=0,w=roz,lz=0;
    while(ile[lz].a==0)lz++;
    long long sum=0;
     //for(int i=lz;i<roz+lz;++i){
      //  cout<<ile[i].a<<' ';
    //}
  //  cout<<"\n";
    for(int i=lz;i<roz+lz;++i){
        sum+=ile[i].a-1;
    }
    //cout<<sum<<' '<<roz<<endl;
    /*
     if(sum-ile[lz].a>=0){
           // cout<<"lol";
            sum-=ile[lz].a;
            w--;
            wczes+=ile[lz].a;
     }
     */
    if(ile[lz].a>1)sum-=ile[lz].a-1;
    for(int i=lz;i<roz+lz;++i){//lz+1
            if(ile[i].a-1>0){
                if(sum-ile[i].a-min(wczes,ile[i].a-1)>=0){
                    sum-=ile[i].a;
                    sum-=min(wczes,ile[i].a-1);
                    wczes-=ile[i].a-1;
                   // wczes=max(0,wczes);
                    w--;
                }
            }
            else if(sum-ile[i].a>=0){
                sum-=ile[i].a;
                wczes+=ile[i].a;
                w--;
            }
    }

    cout<<w;
    return 0;
}
//1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 //2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4