题目描述

最近，哥萨克胡子听说了一个有趣的地方，叫做奇迹之地，那里生长着结满金钱的树木。他决定种下 $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$) —— 树上硬币的初始数量。

输出格式

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

4
1 4 2 3

3

6
1 2 2 3 4 2

0

提示

样例说明

在第二个样例中，无法选择一个 $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 完成