Chocolates

2000ms

262144K

Description:

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.

Input:

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.

Output:

Print the maximum number of chocolates you can buy.

Sample Input:

5
1 2 1 3 6

Sample Output:

Sample Input:

5
3 2 5 4 10

Sample Output:

Sample Input:

4
1 1 1 1

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1139B