Polycarp Training CodeForces - 1165B | Solution 2

Polycarp Training CodeForces – 1165B | Solution

By

Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly 11 problem, during the second day — exactly 22 problems, during the third day — exactly 33 problems, and so on. During the kk-th day he should solve kk problems.

Polycarp has a list of nn contests, the ii-th contest consists of aiai problems. During each day Polycarp has to choose exactly one of the contests he didn’t solve yet and solve it. He solves exactly kk problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least kk problems that Polycarp didn’t solve yet during the kk-th day, then Polycarp stops his training.

How many days Polycarp can train if he chooses the contests optimally?

Input

The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of contests.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2⋅1051≤ai≤2⋅105) — the number of problems in the ii-th contest.

Output

Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.

Examples Input

4
3 1 4 1

Output

3

Input

3
1 1 1

Output

1

Input

5
1 1 1 2 2

Output

2

Solve Code

#include<stdio.h>
#include<stdlib.h>
using namespace std;
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }


    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {

        int m = l+(r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

int main()
{   int n,i,j,tmp,arr[200005],m=0,d;
    scanf("%d",&n);
        for(i=0;i<n;i++)
            {
                scanf("%d",&arr[i]);
            }
         mergeSort(arr, 0, n - 1);
            d=1;
            for(i=0;i<n;i++)
            {
                 if(arr[i]>=d)
                 {
                     d++;
                     m++;

                 }
            }

printf("%d",m);



    return 0;
}

Related Posts