题目描述

一条生产线上从左到右排列着 $n$ 个能量槽，第 $i$ 个能量槽初始存有 $a_i$ 单位能量。

回收系统可以执行若干次操作。每次操作时，控制器输入一个正整数 $k$，系统会从左到右扫描所有能量槽，找到第一个当前能量不少于 $k$ 的能量槽（索引最小的位置），并从这个能量槽中回收 $k$ 单位能量。

为了保证生产线可以继续运行，所有操作结束后，每个能量槽中都必须至少剩下 $1$ 单位能量。

你需要求出，在满足上述限制的前提下，最多能回收多少单位能量。

注意，每次操作选择的 $k$ 可以不同。

输入格式

输入的第一行包含一个正整数 $n$，表示能量槽数量。

输入的第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每个能量槽的初始能量。

输出格式

输出一行一个整数，表示最多能回收的能量总量。

样例 1 输入

4
1 4 2 3

样例 1 输出

3

样例 1 解释

一种最优方案是输入 $k=3$。系统会从左到右找到第一个能量不少于 $3$ 的能量槽，也就是第 $2$ 个能量槽，并回收 $3$ 单位能量。此时所有能量槽仍至少剩下 $1$ 单位能量。

样例 2 输入

6
1 2 2 3 4 2

样例 2 输出

0

样例 2 解释

无论怎样选择第一次操作的 $k$，只要成功回收了正数能量，就会导致之后无法保证所有能量槽最终至少剩下 $1$ 单位能量。因此答案为 $0$。

样例 3

见选手目录下的 reserve/reserve3.in 与 reserve/reserve3.ans。

该样例满足子任务 $1$ 的约束条件。

样例 4

见选手目录下的 reserve/reserve4.in 与 reserve/reserve4.ans。

该样例满足子任务 $2$ 的约束条件。

样例 5

见选手目录下的 reserve/reserve5.in 与 reserve/reserve5.ans。

该样例满足子任务 $3$ 的约束条件。

样例 6

见选手目录下的 reserve/reserve6.in 与 reserve/reserve6.ans。

该样例满足子任务 $4$ 的约束条件。

样例 7

见选手目录下的 reserve/reserve7.in 与 reserve/reserve7.ans。

该样例满足子任务 $5$ 的约束条件。

样例 8

见选手目录下的 reserve/reserve8.in 与 reserve/reserve8.ans。

该样例满足子任务 $6$ 的约束条件。

样例 9

见选手目录下的 reserve/reserve9.in 与 reserve/reserve9.ans。

该样例满足子任务 $7$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1 \le n \le 10^6$；
• $1 \le a_i \le 10^9$。

子任务编号	分值	约束条件
$1$	$4$	$n=2$
$2$	$8$	$n=3$
$3$	$7$	$a_i\le 2$
$4$	$13$	$a_i\le 3$
$5$	$7$	$10\le a_i$
$6$	$19$	$n,a_i\le 1000$
$7$	$42$	无额外限制

本题采用捆绑测试。每个子任务内的测试点必须全部通过，才能获得该子任务分数。