Лимонадна черга#10385

Лимонадна черга

1 секунда

128 мегабайтів

Середня

Спекотного літнього дня на фермі фермер Джон пригощає лимонадом своїх $n$ корів! Усі $n$ корів (зручно пронумеровані $1 \dots n$ ) люблять лимонад, але деякі з них люблять його більше за інших. Зокрема, корова $i$ готова чекати в черзі позаду щонайбільше $w_{i}$ w_i корів, щоб отримати свій лимонад. Прямо зараз усі $n$ корів знаходяться на полях, але щойно фермер Джон задзвонить у свій дзвіночок, вони одразу кинуться до його лимонадного прилавка. Усі вони прибудуть до того, як він почне розливати лимонад, і жодні дві корови не прибудуть одночасно. Більше того, коли корова $i$ прибуває, вона приєднується до черги тоді і тільки тоді, коли в ній уже стоїть не більше $w_{i}$ w_i корів.

Фермер Джон хоче приготувати лимонад заздалегідь, але не хоче, щоб той пропав даремно. Кількість корів, які приєднаються до черги, може залежати від порядку, в якому вони прибувають. Допоможіть йому знайти мінімально можливу кількість корів, які приєднаються до черги.

Вхідні дані

Перший рядок містить ціле число $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Другий рядок містить $n$ цілих чисел $w_{1}, w_{2}, \dots, w_{n} (0 \leq w_{i} \leq 1 0^{9})$ w_1, w_2, \ldots, w_n~(0 \le w_i \le 10^9).

Вихідні дані

Виведіть одне ціле число — мінімальну кількість корів, які приєднаються до черги, серед усіх можливих порядків прибуття корів.

Приклади

Приклад 1

Примітка

У цьому прикладі лише $3$ корови можуть опинитися в черзі, і це найменша можлива кількість. Припустимо, що корови з $w = 7$ w = 7 та $w = 400$ w = 400 прибувають першими та приєднуються до черги. Потім прибуває корова з $w = 1$ w = 1 і йде геть, оскільки в черзі вже стоять $2$ корови. Нарешті, прибувають дві корови з $w = 2$ w = 2: перша з них приєднується до черги, а друга йде геть.