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.

inputFormat

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.

outputFormat

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.

样例

4
1 1 1 1

1