Это сложная версия задачи. Единственное отличие в том, что в этой версии \(n \leq 200000\). Вы можете делать взломы, только если решены обе версии задачи.
В линию выстроены \(n\) настоек, причем настойка \(1\) находится слева, а настойка \(n\) — справа. Каждая настойка увеличит ваше здоровье на \(a_i\), если ее выпить. \(a_i\) может быть отрицательным, что означает, что настойка уменьшит ваше здоровье.
Вы начинаете с \(0\) здоровья и будете идти слева направо, от первой настойки до последней. Для каждой настойки вы можете выбрать, выпить ли ее. Вы должны следить за тем, чтобы ваше здоровье всегда было неотрицательным.
Какое наибольшее количество настоек вы можете выпить?
Выходные данные
Выведите одно целое число — максимальное количество настоек, которое вы можете выпить, чтобы ваше здоровье всегда было неотрицательным.
Примечание
В примере, вы можете выпить \(5\) настоек, приняв настойки \(1\), \(3\), \(4\), \(5\) и \(6\). Невозможно выпить все \(6\) настоек, потому что в какой-то момент ваше здоровье станет отрицательным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 -4 1 -3 1 -3
|
5
|