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
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 500'001;
int tab[N];
bool vis[N];

int main(){
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        int amount;
        scanf("%d", &amount);
        tab[amount]--;
    }
    sort(tab, tab + N - 1);
    int l = -1; int r = N - 1;
    while(!vis[l + 1]){
        l++;
        int max_sum = -tab[l]; int sum = 0;
        for(r; r > l; r--){
            if(sum - tab[r] >= max_sum){
                tab[r] = -(sum - tab[r] - max_sum + 1);
                break;
            }
            sum -= tab[r];
            vis[r] = true;
        }
    }
    printf("%d", l + 1);
    return 0;
}