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.

见题面 Input 部分

见题面 Output 部分

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.