P4379 [USACO18OPEN] Lemonade Line S

It is a hot summer day on the farm, and Farmer John is handing out lemonade to his $N$ cows! All $N$ cows (numbered $1 \dots N$) like lemonade, though some like it more than others. Specifically, cow $i$ is willing to stand behind at most $w_i$ other cows to get lemonade. All $N$ cows are currently out in the field, but as soon as Farmer John rings the cowbell, they will immediately head to the lemonade stand. They will all arrive before Farmer John begins distributing lemonade, and no two cows arrive at the same time. Additionally, when cow $i$ arrives, she joins the line if and only if there are at most $w_i$ cows in the line. Farmer John wants to prepare some amount of lemonade in advance, but he does not want to waste any. The number of cows who line up may depend on their arrival order. Please help him determine, over all possible arrival orders, the minimum possible number of cows that end up in line.

The first line contains $N$. The second line contains $N$ space-separated integers $w_1, w_2, \dots, w_N$. The input guarantees $1 \leq N \leq 10^5$, and for each cow $i$, $0 \leq w_i \leq 10^9$.

Output the minimum possible number of cows in line over all possible arrival orders.

For example, it is possible that only three cows end up in the line (which is also the minimum possible). Suppose the cows with $w = 7$ and $w = 400$ arrive first and wait in line. Then the cow with $w = 1$ arrives and leaves because there are already $2$ cows in line. Next, two cows with $w = 2$ arrive; one stays in line and the other leaves. Problem setter: Dhruv Rohatgi. Translated by ChatGPT 5