Hackathon

Interview

Time limit2sMemory limit512 MB

Summary

Partition N students into the fewest teams so each student's team size does not exceed their limit Xi.

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

Problem

A hackathon will soon be held at Albert's school. N students have expressed interest in participating. For convenience, the students are numbered from 1 to N.

The N participants must be divided into teams, and the organizers want the number of teams to be as small as possible. However, student i will participate only if the number of members in their team, including themselves, is at most Xi. The organizers intend to assign teams so that all N students who expressed interest can participate, and they want to minimize the number of teams.

The teams must satisfy all of the following conditions.

Each student must belong to exactly one team.
Each team contains at least one student.
For every i, the number of members in the team containing student i is at most Xi.

Write a program that finds the minimum possible number of teams when the N students are divided into teams satisfying the conditions above.

Input

The first line gives the number of students N (1 ≤ N ≤ 100,000).

The second line gives N integers, which are X1, X2, ..., XN in order. For every i, 1 ≤ Xi ≤ N.

Output

Print the minimum possible number of teams on the first line.

Hint

For example, if there are 5 students and X1 = 1, X2 = 2, X3 = 5, X4 = 2, X5 = 1, the minimum number of teams is 4.

One can form 5 teams as {1}, {2}, {3}, {4}, {5}, but that is not the minimum. Forming teams as {1}, {3}, {5}, {2, 4} satisfies all the conditions and uses the minimum number of teams.

Examples5

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