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
#include <iostream>
#include<algorithm>

using namespace std;

const int max_n = 5e5;
int n, arr[max_n+1]{0};

int main()
{
    int x, l_num=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>x;
        arr[x-1]++;
        if(arr[x-1] == 1)l_num++;
    }
    for(int i=0; i<n; i++)if(arr[i] == 0)arr[i] = 100000000;
    sort(arr, arr+n);
    int lt=0, rt=l_num-1, result=0, arr_size=l_num, dis;
    while(true){
        int left_side=0;
        while(true){
            if(left_side + arr[lt] <= arr[rt]-1){
                //cout<<left_side<<' '<<arr[lt]<<arr[rt]-1<<'\n';
                left_side += arr[lt];
                lt++;
            }
            else{
                arr[lt] -= arr[rt]-left_side-1;
                break;
            }
        }
        rt--; result++;
        //cout<<lt<<' '<<rt<<'\n';
        if(lt>rt)break;
    }
    cout<<result;
    return 0;
}