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