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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 2 ⋅ 10⁵

1 ≤ a_i ≤ 10⁶

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

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

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

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

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

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

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

5
5
4
1
3
2

2

5
5
4
1
3
3

3

5
1
1
1
1
1

2