← 返回题目列表

Codeforces · 1139/B

B. 巧克力

中文机器翻译题面 查看原题

您去了一家商店,出售 $$$n$$$ 种巧克力。库存有 $$$a_i$$$ 类型的 $$$i$$$ 巧克力。

您拥有无限数量的现金(因此您不受任何价格的限制)并且想要购买尽可能多的巧克力。但是,如果您购买 $$$i$$$ 类型的 $$$x_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$$$),表示每种类型的巧克力数量。

输出

打印出您可以购买的最大巧克力数量。

示例

输入 #1

5
1 2 1 3 6

输出 #1

10

输入 #2

5
3 2 5 4 10

输出 #2

20

输入 #3

4
1 1 1 1

输出 #3

1

注意

在第一个示例中,最佳购买:$$$0 + 0 + 1 + 3 + 6$$$ 巧克力。

在第二个示例中,最佳购买:$$$1 + 2 + 3 + 4 + 10$$$ 巧克力。

在第三个示例中,最佳购买:$$$0 + 0 + 0 + 1$$$ 巧克力。