Lemonade Line#10385
It is a hot summer day on the farm, and Farmer John is serving lemonade to his cows! All cows (conveniently numbered ) like lemonade, but some of them like it more than others. In particular, cow is willing to wait in line behind at most w_i cows to get her lemonade. Right now, all cows are in the fields, but as soon as Farmer John rings his cowbell, they will immediately rush to his lemonade stand. All of them will arrive before he starts serving lemonade, and no two cows will arrive at the same time. Moreover, when cow arrives, she joins the line if and only if there are at most w_i cows already in it.
Farmer John wants to prepare some lemonade in advance, but he does not want to be wasteful. The number of cows who join the line may depend on the order in which they arrive. Help him find the minimum possible number of cows who join the line.
The first line contains an integer n~(1 \le n \le 10^5). The second line contains integers w_1, w_2, \ldots, w_n~(0 \le w_i \le 10^9).
Print one integer — the minimum number of cows who join the line, over all possible orders in which the cows may arrive.
Example 1
In this example, only cows may end up in line, and this is the smallest possible number. Suppose that the cows with w = 7 and w = 400 arrive first and join the line. Then the cow with w = 1 arrives and leaves, since cows are already in line. Finally, the two cows with w = 2 arrive: the first one joins the line, and the second one leaves.