Problem 6D. 桌游
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 6D. 桌游
时间限制: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\).