| Автор: | А. Усманов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
В компании работает N человек. Зарплата i-о сотрудника составляет ai бурлей.
Близится новый год, пора решать кто из сотрудников получит премию. Если на премию будет представлено k человек, то первому будет назначена премия в k бурлей, второму — в k − 1 бурлей и т.д. Порядок назначения на премии совпадает с порядком сотрудников, в котором они перечислены.
Но назначение премии и её выплата не одно и тоже. Дело в том, что размер выплачиваемой премии не может превышать половину зарплаты. То есть, если у сотрудника зарплата 9 бурлей, а назначена премия в 100 бурлей, то он получит лишь 4 бурля (выплата не целого числа бурлей не осуществляется).
Выплата премий не окажет большего влияния на капитал компании, если сумма всех выплаченных премий не превышает сумму зарплат сотрудников, которые не назначались на премию. В тоже время, руководство компании хочет, чтобы как можно больше человек получили новогоднюю премию.
Помогите руководству компании определить максимальное количество человек, которым можно выплатить премию, так, чтобы это не оказало большего влияния на капитал компании.
Требуется написать программу, которая считает количество сотрудников и их зарплаты, и вычислит максимальное количество сотрудников, которые смогут получить премию.
Первая строка содержит одно целое число N — количество работников.
Далее следует N строк, в каждой из которых находится по одному целому числу ai — зарплата i-го работника.
В единственной строке выведите ответ на задачу — максимальное количество сотрудников, которые смогут получить премию.
1 ≤ N ≤ 105
1 ≤ ai ≤ 106
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
|---|---|---|---|
| N | |||
| 1 | 25 | 1 ≤ N ≤ 102 | |
| 2 | 20 | 1 ≤ N ≤ 103 | 1 |
| 3 | 15 | 1 ≤ N ≤ 104 | 1-2 |
| 4 | 40 | 1 ≤ N ≤ 105 | 1-3 |
В первом примере суммарная зарплата двух последних сотрудников равна 5. Этого не хватит, чтобы выдать премию трём другим сотрудникам, так как их премия составит 6 = 3 + 2 + 1.
Во втором примере суммарная зарплата двух последних сотрудников будет равна премии первых двух: 5 = 2 + 2 + 1, так как первый сотрудник не может получать премию больше, чем 5 / 2 = 2.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|