B. Chocolatestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.InputThe 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.OutputPrint the maximum number of chocolates you can buy.ExamplesInput
5
1 2 1 3 6
Output
10Input
5
3 2 5 4 10
Output
20Input
4
1 1 1 1
Output
1NoteIn 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.
5
1 2 1 3 6

10
['greedy', 'implementation', '*1000']