CF1526C2 Potions (Hard Version)

这是该问题的困难版本。唯一的区别在于本版本中 $n \leq 200000$。只有当你解决了两个版本的问题后，才能进行 hack。 有 $n$ 个药水排成一行，药水 $1$ 在最左边，药水 $n$ 在最右边。每个药水在饮用后会使你的生命值增加 $a_i$。$a_i$ 可能为负数，表示该药水会减少你的生命值。 你从 $0$ 生命值开始，从左到右依次经过每个药水。每到一个药水，你可以选择喝掉它或者忽略它。你必须保证你的生命值始终不为负数。 你最多能喝多少个药水？

第一行包含一个整数 $n$（$1 \leq n \leq 200000$），表示药水的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示喝下每个药水后生命值的变化量。

输出一个整数，表示在保证生命值始终不为负数的情况下，最多能喝多少个药水。

对于样例，你可以通过喝第 $1$、$3$、$4$、$5$ 和 $6$ 个药水来喝下 $5$ 个药水。无法喝下全部 $6$ 个药水，因为在某一时刻你的生命值会变为负数。 由 ChatGPT 4.1 翻译