题目描述

强哥最近接手了一家小公交公司的调度工作，他发现公司的公交车运营数据有些混乱。现在有 $n$ 次上下车记录，每次上下车都用一个整数 $a_i$ 表示：若 $a_i$ 是正数，表示上了 $a_i$ 个人；否则表示下了 $a_i$ 个人。

但问题是，车上初始的人数不确定！强哥需要找到一个合理的初始人数，满足以下条件：

1. 在整个运营过程中，车上的人数恒非负（不能出现负数乘客的荒唐情况）
2. 在满足上述条件的前提下，使得最终车上的人数最少

车上初始的人数不确定。强哥绞尽脑汁也想不出好的解决方案，你能帮他找到这个最优的初始人数，从而确定最终车上最少可能剩下多少人吗？

#数据范围

• $1≤n≤2*10^5$
• $-10^9≤a_i≤10^9$

输入格式

• $n$
• $a_1,a_2,a_3,...,a_n$

输出格式

4
3 -5 7 -4

3

#样例解释：

初始乘客人数 $2$ 按照上下车的顺序，乘客人数变化为 $2+3+(-5)+7+(-4)=3$ 人，公交车上的乘客人数始终是一个非负整数。

4
-1 1000000000 1000000000 1000000000

3000000000

提示