得分或解锁

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有一个由 $n$ 张卡牌组成的牌堆，从上到下第 $i$ 张卡牌的数值为 $a_i$。每张卡牌处于“锁定”或“解锁”状态，初始时只有最上方的卡牌已解锁。

游戏按回合进行。每个回合中，你选择一张已经解锁的卡牌，设它的数值为 $v$，并执行以下两种操作之一：

1. 从牌堆顶部开始，将最靠前的 $v$ 张仍被锁定的卡牌解锁；若锁定卡牌不足 $v$ 张，则解锁所有仍被锁定的卡牌；
2. 获得 $v$ 点胜利点数。

无论选择哪一种操作，操作完成后都要从牌堆中移除这张卡牌。

当牌堆中剩余的卡牌全部被锁定，或牌堆为空时，游戏结束。求能够获得的最大胜利点数。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示最大胜利点数。

样例输入 1

2
1 2

样例输出 1

2

样例输入 2

5
2 4 5 0 1

样例输出 2

9

样例输入 3

4
0 4 4 4

样例输出 3

0

数据范围

对于所有数据，$1\le n\le 10^5$，$0\le a_i\le n$。