Solution 1

Since \(x\) is at most \(N\), we can count the occurrence of \(x\) in \(A\) for each \(x=0,1,\dots,N\), and print the maximum \(x\) such that the count is \(x\) or greater.

The time complexity is \(O(N^2)\).

Sample code (Python)

N = int(input())
A = list(map(int, input().split()))
for x in range(N, -1, -1):
    count = 0
    for a in A:
        if a >= x:
            count += 1
    if count >= x:
        print(x)
        break

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& x : A) cin >> x;
    for (int x = N; x >= 0; --x) {
        int count = 0;
        for (auto a : A) {
            if (a >= x) ++count;
        }
        if (count >= x) {
            cout << x << endl;
            break;
        }
    }
}

Solution 2

First, rearrange the elements of \(A\) in descending order to make \(A_1 \geq A_2 \geq \dots \geq A_N\). This is an operation called sort, and many languages provides it as a standard feature. (You may use std::sort in C++ or sort in Python.)

After rearranging \(A\), it contains at least \(i\) elements greater than or equal to \(A_i\), because \(A_1,\dots,A_i\) are all greater than or equal to \(A_i\).

Therefore, the maximum \(x\) such that elements greater than or equal to \(x\) occur at least \(x\) times is the maximum \(x\) with \(A_x \geq x\), which can be found by scanning \(A_x\) from the beginning.

The time complexity is \(O(N \log N)\) where sorting is the bottleneck. While Solution 1 is fast enough under the constraints this time, Solution 2 runs even when \(N\) is about \(10^6\).

Sample code (Python)

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
for x in range(N, 0, -1):
    if A[x - 1] >= x:
        print(x)
        break
else:
    print(0)

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& x : A) cin >> x;
    sort(A.rbegin(), A.rend());
    for (int x = N; x > 0; --x) {
        if (A[x - 1] >= x) {
            cout << x << endl;
            return 0;
        }
    }
    cout << 0 << endl;
}