Cinema Invitation

Interview

Time limit1sMemory limit128 MB

Summary

Given each friend's minimum required number of other attending friends, find the smallest subset size satisfying everyone invited's threshold.

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

Problem

Mirko wants to invite some friends to the cinema for his birthday.

His friends like going to the cinema in large groups. Friend i will go only if, besides Mirko and that friend, at least Zi other friends also go.

Mirko cannot afford to invite everyone, so he wants to invite as few friends as possible. Find the minimum positive number of friends he can invite so that every invited friend's request is satisfied.

Input

The first line contains an integer N, the number of friends. (2 ≤ N ≤ 10 000)

Each of the next N lines contains one integer Zi. (1 ≤ Zi < N) This value is the minimum number of other friends that friend i requires in order to go to the cinema.

Output

Print the minimum number of friends Mirko can invite to the cinema.

Examples3

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