Задача C. Выдача премий ≡

Условие

В компании работает N человек. Зарплата i-о сотрудника составляет a_i бурлей.

Близится новый год, пора решать кто из сотрудников получит премию. Если на премию будет представлено k человек, то первому будет назначена премия в k бурлей, второму — в k − 1 бурлей и т.д. Порядок назначения на премии совпадает с порядком сотрудников, в котором они перечислены.

Но назначение премии и её выплата не одно и тоже. Дело в том, что размер выплачиваемой премии не может превышать половину зарплаты. То есть, если у сотрудника зарплата 9 бурлей, а назначена премия в 100 бурлей, то он получит лишь 4 бурля (выплата не целого числа бурлей не осуществляется).

Выплата премий не окажет большего влияния на капитал компании, если сумма всех выплаченных премий не превышает сумму зарплат сотрудников, которые не назначались на премию. В тоже время, руководство компании хочет, чтобы как можно больше человек получили новогоднюю премию.

Помогите руководству компании определить максимальное количество человек, которым можно выплатить премию, так, чтобы это не оказало большего влияния на капитал компании.

Требуется написать программу, которая считает количество сотрудников и их зарплаты, и вычислит максимальное количество сотрудников, которые смогут получить премию.

Формат входных данных

Первая строка содержит одно целое число N — количество работников.

Далее следует N строк, в каждой из которых находится по одному целому числу a_i — зарплата i-го работника.

Формат выходных данных

В единственной строке выведите ответ на задачу — максимальное количество сотрудников, которые смогут получить премию.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁶

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примерам

В первом примере суммарная зарплата двух последних сотрудников равна 5. Этого не хватит, чтобы выдать премию трём другим сотрудникам, так как их премия составит 6 = 3 + 2 + 1.

Во втором примере суммарная зарплата двух последних сотрудников будет равна премии первых двух: 5 = 2 + 2 + 1, так как первый сотрудник не может получать премию больше, чем 5 / 2 = 2.

Примеры тестов

5
6
4
7
3
2

2

5
5
4
7
3
2

3

5 
1
2
1
1
1

4