CF1526C2.Potions (Hard Version)

This is the hard version of the problem. The only difference is that in this version $n \leq 200000$. You can make hacks only if both versions of the problem are solved.

There are $n$ potions in a line, with potion $1$ on the far left and potion $n$ on the far right. Each potion increases your health by $a_i$ when drunk. $a_i$ can be negative, meaning that the potion decreases your health.

You start with $0$ health, and you will walk from left to right, from the first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?

这是该问题的困难版本。唯一区别在于本版本中 $n \leq 200000$。仅当该问题的两个版本均被解决时，你才可以进行 Hack。

一行中有 $n$ 瓶药水，其中第 $1$ 瓶药水位于最左侧，第 $n$ 瓶药水位于最右侧。每瓶药水被饮用后会使你的生命值增加 $a_i$。$a_i$ 可以为负数，表示该药水会降低你的生命值。

你初始生命值为 $0$，并将从左到右依次经过所有药水（即从第 $1$ 瓶走到第 $n$ 瓶）。在每一瓶药水处，你可以选择饮用它或忽略它，但必须保证在任意时刻你的生命值始终非负。

你最多能饮用多少瓶药水？

The first line contains a single integer $n$ ($1 \leq n \leq 200000$) — the number of potions.

The next line contains $n$ integers $a_1$, $a_2$, ... ,$a_n$ ($-10^9 \leq a_i \leq 10^9$) which represent the change in health after drinking that potion.

第一行包含一个整数 $n$（$1 \leq n \leq 200000$）—— 表示药水的数量。

下一行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$-10^9 \leq a_i \leq 10^9$），表示饮用该药水后生命值的变化量。

Output a single integer, the maximum number of potions you can drink without your health becoming negative.

输出一个整数，表示在生命值不降为负数的前提下，你能喝下的药水的最大数量。

For the sample, you can drink $5$ potions by taking potions $1$, $3$, $4$, $5$ and $6$. It is not possible to drink all $6$ potions because your health will go negative at some point

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