Lemonade Line

Interview

Time limit2sMemory limit512 MB

Summary

Given each cow's maximum tolerated queue length, choose an arrival order that minimizes how many cows end up waiting in line.

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

Problem

It is a hot summer day on the farm, and Farmer John is serving lemonade to his $N$ cows. Every cow likes lemonade, but some like it more than others. The cows are numbered $1$ through $N$ , and cow $i$ is willing to wait in line behind at most $w_i$ other cows to get her lemonade.

Right now all $N$ cows are out in the fields. As soon as Farmer John rings his cowbell, the cows head straight for the lemonade stand. They all arrive before he starts serving, and no two cows arrive at the same time. When cow $i$ arrives, she joins the line if and only if at most $w_i$ cows are already in it. Otherwise she turns away.

Farmer John wants to prepare the lemonade in advance without wasting any. The number of cows who join the line depends on the order in which they arrive. Find the smallest number of cows who can end up in the line.

Input

The first line contains $N$ . The second line contains the $N$ space separated integers $w_1, w_2, \dots, w_N$ . It is guaranteed that $1 \leq N \leq 10^5$ and that $0 \leq w_i \leq 10^9$ for each cow $i$ .

Output

Print, on one line, the smallest number of cows who join the line, taken over all possible arrival orders.

Note

In the first example only three cows end up in line, and no arrival order does better. Suppose the cows with $w = 7$ and $w = 400$ arrive first and wait in line. The cow with $w = 1$ then arrives and turns away, since two cows are already in line. The two cows with $w = 2$ arrive last, one staying and one turning away.

Examples4

Example 1
Input
```
5
7 1 400 2 2
```
Expected output
```
3
```
Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
6
0 0 0 0 0 0
```
Expected output
```
1
```
Example 4
Input
```
8
0 1 2 3 4 5 6 7
```
Expected output
```
4
```