Андрей играет в игру Tanto Cuore.
У него есть колода из \(n\) карт со значениями \(a_1, \ldots, a_n\) сверху вниз. Каждая карта может быть либо заблокирована, либо разблокирована. Первоначально разблокирована только самая верхняя карта.
Ходы происходят по очереди. В каждый ход Андрей выбирает незаблокированную карту из колоды. Пусть значение, записанное на этой карте, равно \(v\). Тогда он выполняет ровно одну из следующих двух операций:
- Разблокировать первые \(v\) заблокированных карт в колоде сверху. Если в колоде меньше \(v\) заблокированных карт, то разблокировать все заблокированные карты.
- Заработать \(v\) очков победы.
В обоих случаях после выполнения операции он убирает карту из колоды.
Игра заканчивается, когда все оставшиеся в колоде карты закрыты или в колоде больше нет карт.
Какое максимальное количество очков победы может заработать Андрей?
Выходные данные
Выведите одно целое число — максимальное количество очков победы, которое может заработать Андрей.
Примечание
В первом примере колода в колоде сначала лежит разблокированная карта, потом заблокированная. Андрей использует первую карту, чтобы разблокировать вторую карту. Затем он использует вторую карту, чтобы заработать \(2\) победных очка.
Во втором примере Андрей может использовать первую карту для разблокировки второй и третьей карт. Затем он использует вторую и третью карты, чтобы заработать \(4+5=9\) победных очков.
В третьем примере Андрей не может разблокировать ни одну карту и получить победные очки с помощью первой карты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
2
|
|
2
|
5
2 4 5 0 1
|
9
|
|
3
|
4
0 4 4 4
|
0
|