310585: CF1855D. Earn or Unlock

D. Earn or Unlocktime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Andrea is playing the game Tanto Cuore.

He has a deck of $n$ cards with values $a_1, \ldots, a_n$ from top to bottom. Each card can be either locked or unlocked. Initially, only the topmost card is unlocked.

The game proceeds in turns. In each turn, Andrea chooses an unlocked card in the deck — the value written on the card is $v$ — and performs exactly one of the following two operations:

1. Unlock the first $v$ locked cards in the deck from the top. If there are less than $v$ locked cards in the deck, then unlock all the locked cards.
2. Earn $v$ victory points.

In both cases, after performing the operation, he removes the card from the deck.

The game ends when all the cards remaining in the deck are locked, or there are no more cards in the deck.

What is the maximum number of victory points Andrea can earn?

Input

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of cards in the deck.

The second line contains $n$ integers $a_1, \ldots, a_n$ ($0 \leq a_1, \ldots, a_n \leq n$) — the values of the cards in the deck.

Output

Output a single integer — the maximum number of victory points Andrea can earn.

ExamplesInput

2
1 2

Output

2

Input

5
2 4 5 0 1

Output

9

Input

4
0 4 4 4

Output

0

Note

In the first sample test, the deck starts as [unlocked, locked]. Then, Andrea uses the first card to unlock the second card. Then he uses the second card to earn $2$ victory points.

In the second sample test, Andrea can use the first card to unlock the second and the third card. Then he uses the second and the third card to earn $4+5=9$ victory points.

In the third sample test, Andrea can't unlock any cards or gain any victory points with the first card.

题目大意：
Andrea 在玩一款名为 "Tanto Cuore" 的游戏。他有一副包含 n 张卡片的牌堆，卡片从上到下依次标有数值 a_1, ..., a_n。每张卡片初始时都是锁定的，只有最顶部的卡片是解锁的。游戏按轮次进行，每轮Andrea可以选择牌堆中一张解锁的卡片，其数值为 v，然后执行以下两个操作之一：
1. 解锁牌堆顶部的前 v 张锁定的卡片。如果牌堆中锁定的卡片少于 v 张，则解锁所有锁定的卡片。
2. 获得数值为 v 的胜利点数。
在执行上述任一操作后，Andrea会从牌堆中移除该卡片。游戏在牌堆中的所有卡片都锁定或牌堆中没有卡片时结束。问Andrea能获得的最大胜利点数是多少？

输入数据格式：
第一行包含一个整数 n（1 ≤ n ≤ 10^5），表示牌堆中的卡片数量。
第二行包含 n 个整数 a_1, ..., a_n（0 ≤ a_1, ..., a_n ≤ n），表示牌堆中卡片的数值。

输出数据格式：
输出一个整数，表示Andrea能获得的最大胜利点数。

示例：
输入：
2
1 2
输出：
2

输入：
5
2 4 5 0 1
输出：
9

输入：
4
0 4 4 4
输出：
0

注意：
在第一个示例中，Andrea首先使用第一张卡片解锁第二张卡片，然后使用第二张卡片获得 2 点胜利点数。
在第二个示例中，Andrea可以使用第一张卡片解锁第二张和第三张卡片，然后使用这两张卡片获得 4+5=9 点胜利点数。
在第三个示例中，Andrea无法使用第一张卡片解锁任何卡片或获得任何胜利点数。题目大意： Andrea 在玩一款名为 "Tanto Cuore" 的游戏。他有一副包含 n 张卡片的牌堆，卡片从上到下依次标有数值 a_1, ..., a_n。每张卡片初始时都是锁定的，只有最顶部的卡片是解锁的。游戏按轮次进行，每轮Andrea可以选择牌堆中一张解锁的卡片，其数值为 v，然后执行以下两个操作之一： 1. 解锁牌堆顶部的前 v 张锁定的卡片。如果牌堆中锁定的卡片少于 v 张，则解锁所有锁定的卡片。 2. 获得数值为 v 的胜利点数。 在执行上述任一操作后，Andrea会从牌堆中移除该卡片。游戏在牌堆中的所有卡片都锁定或牌堆中没有卡片时结束。问Andrea能获得的最大胜利点数是多少？ 输入数据格式： 第一行包含一个整数 n（1 ≤ n ≤ 10^5），表示牌堆中的卡片数量。 第二行包含 n 个整数 a_1, ..., a_n（0 ≤ a_1, ..., a_n ≤ n），表示牌堆中卡片的数值。 输出数据格式： 输出一个整数，表示Andrea能获得的最大胜利点数。 示例： 输入： 2 1 2 输出： 2 输入： 5 2 4 5 0 1 输出： 9 输入： 4 0 4 4 4 输出： 0 注意： 在第一个示例中，Andrea首先使用第一张卡片解锁第二张卡片，然后使用第二张卡片获得 2 点胜利点数。 在第二个示例中，Andrea可以使用第一张卡片解锁第二张和第三张卡片，然后使用这两张卡片获得 4+5=9 点胜利点数。 在第三个示例中，Andrea无法使用第一张卡片解锁任何卡片或获得任何胜利点数。