Codeforces Round 560 (Div. 3) |
---|
Закончено |
Поликарп хочет потренироваться перед очередным важным соревнованием по программированию. В течение первого дня его тренировок он хочет решить ровно $$$1$$$ задачу, в течение второго дня — ровно $$$2$$$ задачи, в течение третьего дня — ровно $$$3$$$ задачи, и так далее. В течение $$$k$$$-го дня он хочет решить ровно $$$k$$$ задач.
У Поликарпа есть список из $$$n$$$ контестов, $$$i$$$-й контест состоит из $$$a_i$$$ задач. В течение каждого дня Поликарп будет выбирать ровно один из контестов, который он еще не решал до этого, и решать его. Он решает ровно $$$k$$$ задач из этого контеста. Остальные задачи исключаются из контеста. Если контестов, состоящих из не менее $$$k$$$ задач, которые Поликарп еще не решал, в течение $$$k$$$-го дня нет, то Поликарп прекращает тренироваться.
Как много дней Поликарп сможет тренироваться, если будет выбирать контесты оптимально?
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество контестов.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — количество задач в $$$i$$$-м контесте.
Выведите одно целое число — максимальное количество дней, которое Поликарп сможет тренироваться, если он будет выбирать контесты оптимально.
4 3 1 4 1
3
3 1 1 1
1
5 1 1 1 2 2
2
Название |
---|