← 返回题目列表

Codeforces · 1526/C2

C2. 药水(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。唯一的区别是在这个版本中 $$$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$$$) 代表饮用该药水后健康状况的变化。

输出

输出一个整数,即在生命值不会变为负值的情况下你可以喝的最大药水数量。

示例

输入 #1

6
4 -4 1 -3 1 -3

输出 #1

5

注意

对于样品,您可以通过服用药水$$$1$$$、$$$3$$$、$$$4$$$、$$$5$$$和$$$6$$$来喝$$$5$$$药水。不可能喝完所有 $$$6$$$ 药水,因为你的健康状况会在某个时刻变为负数