题目描述

你去了一家商店，商店里有 $n$ 种巧克力。第 $i$ 种巧克力有 $a_i$ 块。

你有无限的现金（所以不受价格限制），想要尽可能多地购买巧克力。然而，如果你购买了 $x_i$ 块第 $i$ 种巧克力（显然 $0 \le x_i \le a_i$），那么对于所有 $1 \le j < i$，必须满足以下至少一条：

• $x_j = 0$（你没有买第 $j$ 种巧克力）
• $x_j < x_i$（你买的第 $j$ 种巧克力比第 $i$ 种少）

例如，数组 $x = [0, 0, 1, 2, 10]$ 满足上述要求（假设所有 $a_i \ge x_i$），而数组 $x = [0, 1, 0]$、$x = [5, 5]$ 和 $x = [3, 2]$ 都不满足。

请计算你最多能买多少块巧克力。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示巧克力的种类数。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示每种巧克力的库存数量。

输出格式

输出你最多能买到的巧克力总数。

说明/提示

在第一个样例中，最优方案是购买：$0 + 0 + 1 + 3 + 6$ 块巧克力。

在第二个样例中，最优方案是购买：$1 + 2 + 3 + 4 + 10$ 块巧克力。

在第三个样例中，最优方案是购买：$0 + 0 + 0 + 1$ 块巧克力。

由 ChatGPT 4.1 翻译

样例

5
1 2 1 3 6

10

5
3 2 5 4 10

20

4
1 1 1 1

1