1139_B. Chocolates
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 ≤ x_i ≤ a_i), then for all 1 ≤ 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 ≥ 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 ≤ n ≤ 2 ⋅ 10^5), denoting the number of types of chocolate.

The next line contains n integers a_i (1 ≤ a_i ≤ 10^9), denoting the number of chocolates of each type.

Output

Print the maximum number of chocolates you can buy.

Examples

Input


5
1 2 1 3 6


Output


10

Input


5
3 2 5 4 10


Output


20

Input


4
1 1 1 1


Output


1

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.
```python
n = int(input())
a = list(map(int,input().split()))
max = a[len(a)-1]
sum = max
for i in range(len(a)-2,-1,-1):
    # print(max)
    if (max<=0):
        break
    if (a[i]>=max):
        # print(a[i])
        max = max-1
        sum += max
    else:
        # print(a[i])
        max = a[i]
        sum += max
print(sum)
```