P15034 [UOI 2021 II Stage] 奇迹之地

最近，哥萨克胡子听说了一个有趣的地方，叫做奇迹之地，那里生长着结满金钱的树木。他决定种下 $n$ 棵钱树，并在第二年收获。 当胡子回到奇迹之地视察时，他发现每棵树上至少长出了一枚硬币，并且第 $i$ 棵树上的硬币数量为 $a_i$。他觉得亲自收获太费时间，于是制造了一台机器，这台机器可以多次执行以下操作： - 选择一个正整数 $k$； - 找到当前硬币数至少为 $k$ 的第一棵树（即索引最小的树）； - 从该树上取走 $k$ 枚硬币。 但在钱树养护手册中，哥萨克胡子了解到，收获后每棵树上必须至少留下一枚硬币，否则它们明年将不会结果。 现在哥萨克胡子想知道，经过若干次操作后，这台机器最多能收获多少硬币。 请注意，不同操作中选择的数字 $k$ 可以不同。

第一行包含一个整数 $n$ ($1 \leq n \leq 10^6$) —— 奇迹之地上的树的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) —— 树上硬币的初始数量。

输出一个整数 —— 机器经过一系列操作后最多能收集到的硬币数量，同时确保每棵树上至少留下一枚硬币。

### 样例说明 在第二个样例中，无法选择一个 $k$ 使得能收集到至少一枚硬币，同时还能在每个树上都留下硬币。 ### 评分细则 - （4 分）： $n = 2$； - （8 分）： $n = 3$； - （7 分）： $a_i \leq 2$； - （13 分）： $a_i \leq 3$； - （7 分）： $10 \leq a_i$； - （19 分）： $a_i, n \leq 1\,000$； - （42 分）： 无额外限制。 翻译由 DeepSeek V3 完成