← 返回题目列表

Codeforces · 1854/B

B. 赚取或解锁

中文机器翻译题面 查看原题

Andrea 正在玩 Tanto Cuore 游戏。

他有一副 $$$n$$$ 牌,从上到下的值为 $$$a_1、\ldots、a_n$$$。每张卡都可以锁定或解锁。最初,只有最上面的卡被解锁。

游戏轮流进行。在每一回合中,Andrea 在牌组中选择一张未锁定的卡牌(卡上写的值为 $$$v$$$),并执行以下两个操作之一:

1. 从顶部解锁牌组中第一张 $$$v$$$ 锁定的牌。如果牌组中的锁定卡牌少于$$$v$$$,则解锁所有锁定的卡牌。
2. 赚取 $$$v$$$ 胜利积分。

当牌组中剩余的所有牌都被锁定,或者牌组中没有更多牌时,游戏结束。

安德里亚最多可以获得多少胜利点?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 这副牌中的牌数。

第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_1, \ldots, a_n \leq n$$$) — 这副牌中的牌的值。

输出

输出一个整数——Andrea 可以获得的最大胜利点数。

示例

输入 #1

2
1 2

输出 #1

2

输入 #2

5
2 4 5 0 1

输出 #2

9

输入 #3

4
0 4 4 4

输出 #3

0

注意

在第一个样本测试中,牌组开始时为[解锁,锁定]。然后,安德里亚使用第一张卡解锁第二张卡。然后他使用第二张牌赚取 $$$2$$$ 胜利积分。

在第二个样本测试中,Andrea可以使用第一张卡解锁第二张和第三张卡。然后他使用第二张和第三张牌获得$$$4+5=9$$$胜利积分。

在第三个样本测试中,Andrea 无法使用第一张卡牌解锁任何卡牌或获得任何胜利点。