Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time I am looking for a solution for the following problem:

Find the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time.

Consider the following sequence:
$$
3, 1, 6, 1, 5
$$
The answer here is $3$, with $6, 5, 3$ being in the set found. The value of $N$ is not a given - we're looking for the largest $N$.
So far, I came up with three solutions:

Sort the sequence and go from the top.
Use a modified version of quickselect.
Use a modified version of BST where elements bigger than the current $n$ are inserted, and elements smaller than the new $N$ are removed.

1 and 3 are more or less $n\log n$ (though I'd expect 3 to be faster), 2 is best case $n$, worst case $n^2$.
Our teacher told us it's possible to do it in a reliable $n$ time. What is the algorithm for the linear solution, if there's one?
Let $n$ denote the length of the array. We will find the largest $N$ such that there are at least $N$ elements whose value is at least $N$.
Make a pass through the array, counting the number of elements of value $1,2,\ldots,n$; if any element has value larger than $n$, count it as $n$.
Using this, determine, for each value $m \in \{1,2,\ldots,n\}$, the number of elements whose value is at least $m$.
Now you can easily determine the solution.