Codeforces Round 548 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

implementation

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Chocolates

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2023 13:39:30 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|