题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

你打算在给定的滑冰赛道上进行滑冰练习。该赛道由起点、$N$ 个中间点和终点组成。练习开始于起点，起始速度为 $0$，然后按照编号递增的顺序依次经过第 $1$ 个中间点到第 $N$ 个中间点，最后以速度 $0$ 到达终点后结束。

每个中间点都有一个速度限制 $V_i$。在前往下一个中间点的过程中，必须控制速度不超过该点的速度限制。你可以任意提升速度，但若要降低速度，每次只能从上一个经过的中间点的速度减少 $1$。此外，除起点和终点外，任何位置上的速度不能为 $0$。保持原有速度也是允许的。

本次练习的成果由各中间点的速度之和决定，因此你希望最大化这个总和。给定赛道的速度限制，计算你在该赛道中最多能取得的练习成果。

例如，在中间点数为 $3$，速度限制为 $V = [2, 3, 1]$ 的情况下，如果你在第 $2$ 个中间点以速度 $3$ 前进，就无法将速度调整为不超过第 $3$ 个中间点限制（即 $1$）的数值。因此，这样的安排不可行。

一种可行的安排是按顺序调整速度为 $[2, 2, 1]$，其速度之和为 $2 + 2 + 1 = 5$。其他可行的安排还包括 $[1, 1, 1]$ 和 $[1, 2, 1]$，但它们的速度之和也不会超过 $5$。因此，在此赛道中可以获得的最大练习成果为 $5$。

输入格式

第一行输入一个整数 $N$。
第二行输入 $V_1, V_2, \dots, V_N$，各数之间以空格分隔。

输出格式

输出一个整数，表示最大可获得的练习成果（即速度总和）。

3
2 3 1

5

4
23 7 1 5

7

提示

限制条件

• 所有给定的数都是整数。
• $1 \leq N \leq 500\,000$
• $1 \leq V_i \leq 1\,000\,000\,000 \quad (1 \leq i \leq N)$

子任务

1. （8 分）$N \leq 8,\ V_i \leq 8 \quad (1 \leq i \leq N)$
2. （12 分）$N \leq 500,\ V_i \leq 500 \quad (1 \leq i \leq N)$
3. （17 分）$N \leq 5\,000,\ V_i \leq 5\,000 \quad (1 \leq i \leq N)$
4. （10 分）$N \leq 5\,000$
5. （53 分）无附加限制

翻译由 ChatGPT-4o 完成