题目描述

小华在探索神秘洞穴时遭遇了一个奇特的防御系统：$n$ 个生物紧密堆叠形成了一座生物塔！塔的结构从下到上编号为 $1$ 到 $n$，第 $i$ 个生物位于第 $i$ 层，初始拥有 $a_i$ 点生命值。

小华每次可以选择塔中任意一个生物进行攻击，造成 $1$ 点伤害。当某个生物的生命值降至零或以下时，该生物会被消灭，其上方的所有生物会向下坠落并重新堆叠成一座新的塔。

坠落过程中，新堆叠最底层的生物会受到坠落冲击，伤害值等于坠落前它下方生物的数量（包括刚被消灭的那个生物）。如果这次冲击导致该生物死亡，坠落过程会继续向上传导，形成连锁反应。

例如，考虑一个生命值为 $[3, 2, 1, 4, 4, 3, 2]$ 的生物塔。如果小华攻击第四层的生物（生命值 $4$），该生物死亡后：

1. 上方的 $[4, 3, 2]$ 会坠落形成新塔
2. 新塔最底层的生物受到 $4$ 点坠落伤害而死亡，伤害从新塔向上传导
3. 上方的 $[3, 2]$ 继续坠落，最底层生物受到 $1$ 点坠落伤害

最终形成两座塔： $[3, 2, 1]$ 和 $[2, 2]$。

小华的武器耐久有限，他需要找出摧毁整座生物塔所需的最少攻击次数。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示生物数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示从底层到顶层的生物初始生命值。

输出格式

输出一个整数，表示消灭所有生物所需的最少攻击次数。

输入输出样例

输入样例 1

5
3 1 4 1 2

输出样例 1

7

输入样例 2

4
1 1 1 1

输出样例 2

1

输入样例 3

6
1 2 1 3 5 2

输出样例 3

7

输入样例 4

6
3 1 1 3 2 1

输出样例 4

5

输入样例 5

3
1000000000 1000000000 1000000000

输出样例 5

2999999998

样例解释

样例 1说明：

初始塔：$[3,1,4,1,2]$

最优攻击策略：

1. 攻击第 $2$ 层（生命值 $1$ ）$\rightarrow$ 塔分裂为 $[3]$ 和 $[2,1,2]$
2. 攻击第二座塔第 $2$ 层（生命值 $1$ ）$\rightarrow$ 塔变为 $[3]$ 和 $[2]$
3. 攻击第一座塔剩余的一只生物（ $3$ 次）+攻击第二座塔剩余的一只生物（ $2$ 次）

总计：$1 + 1 + 3 + 2 = 7$ 次攻击

样例 2说明：只需攻击最底层的生物一次，引发的连锁反应就会让整个塔瞬间崩塌。

数据范围

• 对于 $30 \%$ 的数据，满足：$1 \leq n \leq 20$，$1 \leq a_i \leq 10^9$
• 对于 $100 \%$ 的数据，满足：$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$