Start: Jul, 04, 2018 08:00:00
2018年度暑期短学期第二天
End: Jul, 05, 2018 08:00:00
Time elapsed:
Time remaining:

CCJ老酋长之旅 2172

Time Limit:  2 s      Memory Limit:   128 MB
Submission:756     AC:247     Score:0

Description

CCJ是一个老酋长,但他不相信自己是老酋长,你需要告诉他酋长值使其相信他是个老酋长。酋长值的计算方法为:

刚开始CCJ的幸运值为0,他一共会走n步,每走一步都会抽取一张卡牌,卡牌上的数字为a,然后他的幸运值就会加上a(a>0时为祝福点,a<0时为诅咒点)。

但由于他丑,正义的发牌人HDH给CCJ发了一张厄运卡,效果是他每一步获得的祝福点数减半。

一旦某回合结束后幸运值为负数,他的酋长值就会加上1。

现在给你每个回合CCJ抽到的卡牌数字,请你求出CCJ最后的酋长值。


Input

输入有多组数据,每一组先输入一个n,代表走n步,接下来一行输入n个数,代表抽到的卡牌上的数字。

Output

输出CCJ的酋长值。

Samples

input
3 -2 2 3 4 8 -6 2 3
output
2 2