레이팅 미적용1 \(s / 64\) \(MB / 50\) points
How do we evaluate the success of a scientist? By the number of published papers or by
their impact - more precisely, the number of citations? Both elements matter. We say that a
scientific paper has a citation score \(C\) if other scientists cited the paper in question in their
paper (referred to it) a total of \(C\) times. One of the possible metrics of the success of
scientists is their h-index that takes into account both the amount of papers and their citation
scores.
A scientist’s h-index is defined as the largest number \(H\) with the following properties: the
scientist can choose \(H\) papers such that their citation score is at least \(H\)
. For example, if a
scientist wrote 10 papers such that each of them has been cited 10 or more times, their
h-index is (at least) 10.
Write a programme that inputs the citation scores of all papers of a given scientist and
outputs their h-index.
The first line of input contains the positive integer \(N\)
(1 ≤ \(N\)
≤ 500 000), the number of papers
of a given scientist.
The following line contains \(N\)
non-negative integers from the interval [0, 1 000 000], the
citation scores of the respective papers.
The first and only line of output must contain the required h-index.
5
1 1 4 8 1
5
8 5 3 4 10output
2
4Clarification of the first test case: The scientist has two papers with citation scores larger than or
equal to 2 (the papers with citation scores 4 and 8).
Clarification of the second test case: The scientist has four papers with citation scores larger than or
equal to 4 (the papers with citation scores 8, 5, 4 and 10).