H-Index

Interview

Time limit1sMemory limit512 MB

Summary

Given the citation counts of n papers, find the largest H such that at least H papers have at least H citations each.

Level: Medium4 of 10
Topics: Sorting, Array, Greedy, Binary search
Solved: No attempts yet

Problem

In research, it is tough to determine how good of a researcher you are. One way that people determine how good you are is by looking at your $H$ -Index.

Each paper has a certain number of citations. Your $H$ -Index is the largest number $H$ such that you have $H$ papers with at least $H$ citations. Given the number of citations on each paper you have written, what is your $H$ -Index?

Input

The first line of input contains a single integer $n$ ( $1 \leq n \leq 100\,000$ ), which is the number of papers you have written.

The next $n$ lines describe the papers. Each of these lines contains a single integer $c$ ( $0 \leq c \leq 1\,000\,000\,000$ ), which is the number of citations that this paper has.

Output

Display your $H$ -Index.

Examples3

Example 1
Input
```
5
7
1
2
1
5
```
Expected output
```
2
```
Example 2
Input
```
5
7
1
3
1
5
```
Expected output
```
3
```
Example 3
Input
```
3
4
2
3
```
Expected output
```
2
```