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 无法使用第一张卡牌解锁任何卡牌或获得任何胜利点。