您去了一家商店,出售 $$$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$$$ 巧克力。