桌游

桌游

时间限制:\(1s\)

空间限制:\(128MB\)

题目描述

如你所见,最近\(lhy\)由于七圣召唤而沉迷于桌游。现在,他的桌上有\(n\)张卡牌上下叠成一堆,编号1~n,卡牌有行动牌和技能牌两种。每张技能牌都会有一个伤害值\(a_i \ne 0\),方便起见,行动牌的伤害值\(a_i=0\).
每次\(lhy\)可以从牌堆顶部获取一张牌,如果这是一张技能牌,那么\(lhy\)可以选择弃置之,亦可将其置于手牌区顶部;
如果获得的是一张行动牌,那么直接弃置这张牌,然后\(lhy\)可以选择将手牌区顶部的牌弃置(如果有的话),并造成\(a_i\)点伤害,也可以选择直接跳过。
现在你看到了整个牌堆,请问\(lhy\)最多可以打出多少伤害。

数据格式

输入

第一行,一个正整数\(n\),表示牌的数量。
第二行,\(n\)个非负整数,表示牌的伤害值,如果\(a_i=0\),它是行动牌,否则,它是技能牌。

输出

一个非负整数,表示最大的伤害。

样例

输入1

5
3 3 3 0 0

输出1

6

输入2

6
0 3 3 0 0 3

输出2

6

输入3

7
1 2 5 0 4 3 0

输出3

9

数据范围及约定

\(1 \le n \le 10^5\).

信息

ID
1542
难度
9
分类
(无)
标签
(无)
递交数
2
已通过
1
通过率
50%
上传者