В пекарне «У Матроны» работает один пекарь, и за утро он должен испечь n заказов пирожков. Для каждого заказа известно время ti — сколько минут займёт его приготовление.
Пирожки нельзя долго держать на прилавке: клиент заберёт свой заказ горячим, только если время ожидания не превысило времени его приготовления. Иначе пирожки остынут — и клиент уйдёт расстроенным.
Временем ожидания клиента считается суммарное время приготовления всех заказов, которые пекарь взял в работу до его заказа. Клиент остаётся доволен, если это время не больше времени приготовления его собственного пирожка.
Матрона может сама решать, в каком порядке брать заказы в работу. Помогите ей выбрать такой порядок, чтобы максимальное число клиентов ушло довольными.
Формат входных данных
В первой строке — целое число n (1 ≤ n ≤ 105) — количество заказов.
Во второй строке — n целых чисел ti (1 ≤ ti ≤ 109), разделённых пробелами, — время приготовления каждого заказа.
Формат выходных данных
Одно целое число — максимальное количество довольных клиентов.
| № | Входные данные | Выходные данные |
|
1
|
5
15 2 1 5 3
|
4
|