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
94
95
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <utility>

using namespace std;

int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, w = 0, w1 = 0;
    cin >> n;
    int tab[n+1], l[n+1] = {0};
    vector <pair <int, int>> ciagi;
    vector <pair <int, int>> cos;

    for(int i=0; i<n; i++)
    {
        cin >> tab[i];
        l[tab[i]]++;
        if(l[tab[i]] > 1)    w = 1;
        if(tab[i] != tab[i]-1)      w1 = 1;
    }


    if(w1 == 0)
    {
        cout << 1;
        return 0;
    } 
    if(w == 0)
    {
        cout << n;
        return 0;
    }


    for(int i=0; i<=n; i++)
    {
        if(l[i] != 0)
        {
            cos.push_back(make_pair(l[i], i));
        }
    }

    sort(cos.begin(), cos.end());

    int beg = cos.size()-1, end = 0; 

    if(cos[beg].first > n/2)
    {
        cout << 1; 
        return 0;
    }

    w = 0;
    ciagi.push_back(make_pair(cos[beg].first, 0));

    while(beg > end)
    {
        if(ciagi[w].second == ciagi[w].first-1)
        {
            beg--;
            w++;
            ciagi.push_back(make_pair(cos[beg].first, 0));
        }
        else
        {
            if(cos[end].first + ciagi[w].second < ciagi[w].first)
            {
                ciagi[w].second += cos[end].first;
                end++;
            }
            else
            {
                cos[end].first -= ciagi[w].first - ciagi[w].second - 1;
                ciagi[w].second = ciagi[w].first-1;
                w++;
                beg--;
                ciagi.push_back(make_pair(cos[beg].first, 0));
            }
        }
    }

    cout << ciagi.size();




    return 0;
}