Chocolates

题意翻译

你去了一家商店，发现这里有$n$种巧克力。第$i$种巧克力有$a_{i}$的库存。 你有无数的钞票（所以你不会受到任何价格的限制）并且想买尽可能多的巧克力。然而，如果你买了$x_{i}$个第$i$种的巧克力（显然$0\leq x_{i}\leq a_{i}$），那么对于所有的$1 \le j < i$都必须满足下述的至少一个约束条件： - $x_j = 0$（第$i$种巧克力你买了0个） - $x_j < x_i$（相比第$i$种，你买了更少的第$j$种巧克力） 比如，数组$x = [0, 0, 1, 2, 10]$满足上述要求（假设$a_i \ge x_i$），而数组$x = [0, 1, 0]$，$x = [5, 5]$，$x = [3, 2]$并不满足。 请计算你最多能买多少巧克力。

题目描述

You went to the store, selling $ n $ types of chocolates. There are $ a_i $ chocolates of type $ i $ in stock. You have unlimited amount of cash (so you are not restricted by any prices) and want to buy as many chocolates as possible. However if you buy $ x_i $ chocolates of type $ i $ (clearly, $ 0 \le x_i \le a_i $ ), then for all $ 1 \le j < i $ at least one of the following must hold: - $ x_j = 0 $ (you bought zero chocolates of type $ j $ ) - $ x_j < x_i $ (you bought less chocolates of type $ j $ than of type $ i $ ) For example, the array $ x = [0, 0, 1, 2, 10] $ satisfies the requirement above (assuming that all $ a_i \ge x_i $ ), while arrays $ x = [0, 1, 0] $ , $ x = [5, 5] $ and $ x = [3, 2] $ don't. Calculate the maximum number of chocolates you can buy.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ), denoting the number of types of chocolate. The next line contains $ n $ integers $ a_i $ ( $ 1 \le a_i \le 10^9 $ ), denoting the number of chocolates of each type.

输出格式

Print the maximum number of chocolates you can buy.

输入输出样例

输入样例 #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

说明

In the first example, it is optimal to buy: $ 0 + 0 + 1 + 3 + 6 $ chocolates. In the second example, it is optimal to buy: $ 1 + 2 + 3 + 4 + 10 $ chocolates. In the third example, it is optimal to buy: $ 0 + 0 + 0 + 1 $ chocolates.