Sungji's Birthday Party

Interview

Time limit2sMemory limit128 MB

Summary

Given N students each requiring a minimum number of other attendees to be satisfied, find the smallest group of students that can be invited so every invited student's requirement is met.

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

Problem

Sungji's birthday is three days away. At midnight between Sunday and Monday, a birthday party will be held in room 902. Sungji always attends, and some students may be invited.

There are N students who want to attend. Student i is satisfied only if, when that student is invited, at least k_i other students also attend, not counting that student or Sungji.

Sungji wants to invite as few students as possible while satisfying every invited student's requirement. Given N and all k_i values, find the minimum number of students to invite.

Input

The first line contains the number of students N. (1 <= N <= 10,000)

Each of the next N lines contains one student's value k_i.

Output

Print the minimum number of students that can be invited while satisfying all invited students.

Hint

When two students both have k = 1, inviting only one student does not work because that student has no other student beside them. Inviting both students works because each student has exactly one other student present.

Examples2

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