Given N citation counts, compute the largest H with at least H papers cited at least H times.
Easy3SortingInterviewNo attempts yetTime limit1sMemory limit256 MBHow do you measure a scientist's success? You can count the papers they published, or you can count the impact of those papers, that is, how often other scientists cite them. Both numbers matter. A paper has citation score C if other scientists cited it C times in their own papers. The h-index is one metric that reflects the number of papers and their citation scores at the same time.
The h-index is the largest integer H with the following property: the scientist can choose H papers whose citation score is at least H. For example, if a scientist wrote 10 papers and each of them was cited 10 or more times, that scientist's h-index is at least 10.
Given the citation scores of every paper a scientist wrote, write a program that computes the h-index.
The first line contains the number of papers N (1≤N≤500,000).
The second line contains N citation scores separated by spaces. Each citation score is an integer between 0 and 1,000,000.
Print the h-index on the first line.
In the first example two papers have a citation score of 2 or more, the one cited 4 times and the one cited 8 times. Only one paper has a citation score of 3 or more, so the h-index is 2.