C2. Настойки (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие в том, что в этой версии $$$n \leq 200000$$$. Вы можете делать взломы, только если решены обе версии задачи.

В линию выстроены $$$n$$$ настоек, причем настойка $$$1$$$ находится слева, а настойка $$$n$$$ — справа. Каждая настойка увеличит ваше здоровье на $$$a_i$$$, если ее выпить. $$$a_i$$$ может быть отрицательным, что означает, что настойка уменьшит ваше здоровье.

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

Какое наибольшее количество настоек вы можете выпить?

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 200000$$$) — количество настоек.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ... ,$$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$), которые обозначают изменения здоровья после употребления данных настоек.

Выходные данные

Выведите одно целое число — максимальное количество настоек, которое вы можете выпить, чтобы ваше здоровье всегда было неотрицательным.

Пример
Входные данные
6
4 -4 1 -3 1 -3
Выходные данные
5
Примечание

В примере, вы можете выпить $$$5$$$ настоек, приняв настойки $$$1$$$, $$$3$$$, $$$4$$$, $$$5$$$ и $$$6$$$. Невозможно выпить все $$$6$$$ настоек, потому что в какой-то момент ваше здоровье станет отрицательным.