#B3628. 机器猫斗恶龙

机器猫斗恶龙

题目描述

机器猫出门斗恶龙了!他需要通过 nn 个关卡。

每个关卡要么是与怪物战斗,扣除一定的血量;要么是营地,给机器猫增加一定的血量。

在旅途中,机器猫任意时刻的血量不能低于或等于 00。问机器猫至少需要多少的初始血量,才能完成任务。

血量为正整数。

输入格式

第一行,一个正整数 nn,表示关卡数量。

第二行,共 nn 个整数 aia_i,表示每个关卡。

  • ai>0a_i>0,则表示这个关卡是营地,增加 aia_i 的血量
  • ai<0a_i<0,则表示这个关卡是战斗,机器猫血量代价为 aia_i

输出格式

仅一行,一个正整数,表示机器猫需要的初始血量。

3
-100 -200 -300
601
5
-200 -300 1000 -100 -100
501

提示

样例解释

第二组样例:机器猫带着 501501 点血量出门,两场战斗之后剩下 11,恢复到 10011001,两场战斗之后为 801801,完成任务。

数据规模与约定

对于 100%100\% 的数据,n100000,1ai1000n\leq 100000, 1\leq |a_i|\leq 1000