Minimum Lemon Soda Line

On a hot summer day at the farm, Farmer John is ready to serve lemon soda to his N cows, numbered from 1 to N. Each cow i is willing to wait in line only if there are at most \(w_i\) cows in front of her. When a cow arrives, she will join the line if and only if the current number of cows in line is at most \(w_i\); otherwise, she does not join.

Since the cows arrive one at a time and no two cows arrive simultaneously, the final number of cows in line depends on the order in which they arrive. Farmer John wants to be sure to prepare only as much soda as needed. In the worst-case (or, rather, the best-case from his perspective), what is the minimum possible number of cows that could be waiting in line over all possible arrival orders?

Note: The arrival order can be chosen arbitrarily to minimize the final line size.

Hint: By ordering the cows so that those with high tolerance (large \(w_i\)) come first, you may force the more choosy cows (with smaller \(w_i\)) to arrive when the line is already too long, causing them to refrain from joining.

inputFormat

The first line contains a single integer \(N\) (the number of cows). The second line contains \(N\) space-separated nonnegative integers \(w_1, w_2, \dots, w_N\), where each \(w_i\) represents the maximum number of cows that cow \(i\) is willing to stand behind.

outputFormat

Output a single integer representing the minimum possible number of cows that join the line over all possible arrival orders.

sample

2
1 0

1