虎哥去了一家商店，发现这里有n种巧克力。第i种巧克力有ai的库存。
虎哥准备了充足的钱，他想买尽可能多的巧克力。然而，如果买了xi个第i种的巧克力（显然0≤xi≤ai），那么对于所有的1≤j<i都必须满足下述的至少一个约束条件：

• (1)xj=0（第i种巧克力买了0个）
• (2)xj<xi (相比第i种,只能买了更少的第j种巧克力）

比如，数组x=[0,0,1,2,10]满足上述要求（假设ai≥xi），而数组x=[0,1,0]，x=[5,5]，x=[3,2]并不满足。
请计算最多能买多少巧克力。

第一行包含一个整数n (1≤n≤2e5),表示巧克力的种类。
下一行包含n个整数ai(1≤ai≤1e9),表示每种巧克力的数量。

一个整数，表示能购买的巧克力的最大数量

5
1 2 1 3 6

10

样例2
输入：
5
3 2 5 4 10
输出：
20

样例3
输入：
4
1 1 1 1
输出：
1

样例1中，最优购买方案为：0+0+1+3+6
样例2中，最优购买方案为：1+2+3+4+10
样例3中，最优购买方案为：0+0+0+1