Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

B. Chocolates
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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.