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.

Difficulty: interview

Starter code:

Solutions:
rr = lambda: input().strip()
rri = lambda: int(rr())
rrm = lambda: list(map(int, rr().split()))

def solve(N, A):
    ans = 0
    prev = float('inf')
    for x in reversed(A):
        x = min(x, prev - 1)
        ans += max(x, 0)
        prev = x
    return ans

for tc in range(1):#rri()):
    N = rri()
    A = rrm()
    print(solve(N, A))


import getpass
import sys

if getpass.getuser() != 'frohenk':
    filename = 'half'
    # sys.stdin = open('input.txt')
    # sys.stdout = open('output.txt', 'w')
else:
    sys.stdin = open('input.txt')
    # sys.stdin.close()

import math
import string
import re
import math
import random
from decimal import Decimal, getcontext


def ria():
    return [int(i) for i in input().split()]


n = ria()[0]
ar = [i for i in reversed(ria())]
p = ar[0]
sm = ar[0]
for i in range(1,n):
    cr=min(max(0,p-1),ar[i])
    # print(cr)
    p=cr
    sm+=cr
print(sm)

n = int(input())

t = list(map(int, input().split()))

v = [0] * n
v[-1] = t[-1]
for i in range(n - 1 - 1, 0 - 1, -1):
    v[i] = max(min(v[i + 1] - 1, t[i]), 0)

print(sum(v))

n = int(input())
a = list(map(int, input().split()))
ans = 0
mx = a[-1] + 1
for i in range(n-1,-1,-1):
    ans += max(0, min(mx-1, a[i]))
    mx = min(mx-1, a[i])
print(ans)

#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)

isdebug = False
try :
    #raise ModuleNotFoundError
    import pylint
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
    isdebug = True
except Exception:
    def dprint(*args, **kwargs):
        pass


def red_inout():
    inId = 0
    outId = 0
    if not isdebug:
        inId = 0
        outId = 0
    if inId>0:
        dprint('use input', inId)
        try:
            f = open('input'+ str(inId) + '.txt', 'r')
            sys.stdin = f #标准输出重定向至文件
        except Exception:
            dprint('invalid input file')
    if outId>0:
        dprint('use output', outId)
        try:
            f = open('stdout'+ str(outId) + '.txt', 'w')
            sys.stdout = f #标准输出重定向至文件
        except Exception:
            dprint('invalid output file')
            
        atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit

if isdebug and len(sys.argv) == 1:
    red_inout()

def getIntList():
    return list(map(int, input().split()))            

def solve(): 
    pass
    
T_ = 1    
#T_, = getIntList()

for iii_ in range(T_):
    #solve()
    N,  = getIntList()
    #print(N)
    za =  getIntList()
    r = 0
    now = 10**10
    for i in range(N-1, -1, -1):
        x = min(now-1, za[i])
        if x<=0: break
        now = x
        r+=x
    print(r)


n=int(input())
l=list(map(int,input().split()))
ans=0
curr=1000000001
for i in range(n-1,-1,-1):
         if(l[i]<curr):
                  curr=l[i]
         elif(curr>0):
                  curr-=1
         ans+=curr
print(ans)

import math
n = int(input())
a = list(map(int, input().split()))
a = list(reversed(a))
s = 0
m = math.inf
for i in range(len(a)):
    m = min(max(m-1, 0), a[i])
    s +=m
print(s)

n = int(input())
a = list(map(int, input().split()))
c = a[-1]
res = c
for i in a[::-1][1:]:
    if i < c:
        res += i
        c = i
    else:
        if c == 0:
            break
        res += c - 1
        c -= 1
print(res)

n = int(input())
A = [int(i) for i in input().split()]
ans = 0
curmax = 10**10
for i in range(n-1, -1, -1):
    if curmax==0:
        continue
    if A[i] < curmax:
        ans += A[i]
        curmax = A[i]
    else:
        ans += curmax-1
        curmax-=1
print(ans)
    
    


n = int(input())
a = list(map(int, input().split()))
maxi = 10**11
ans = 0
for i in range(n - 1, -1, -1):
    maxi = max(min(a[i], maxi - 1), 0)
    ans += maxi
print(ans)


n = int(input())
A = list(map(int, input().split()))
cnt = 0
z = float('inf')
for i in range(n - 1, -1, -1):
    if z > A[i]:
        z = min(z, A[i])
        cnt += z
    else:
        z -= 1
        z = max(0, z)
        cnt += z
print(cnt)

n = int(input())
a = list(map(int, input().split()))

r = 10**10
ans = 0
for i in range(n):
    r = max(min(r - 1, a[n - i - 1]), 0)
    ans += r
print(ans)


n=int(input())
arr=list(map(int,input().split()))
ans=arr[-1]
val=max(arr[-1]-1,0)
for i in range(n-2,-1,-1):
	if(arr[i]>val):
		ans+=val
		val=max(val-1,0)
	else:
		ans+=arr[i]
		val=max(arr[i]-1,0)
print(ans)


n = int(input())
l = [*map(int, input().split())]
m = [e for e in l]
for i in range(n - 2, -1, -1):
    m[i] = max(0, min(m[i], m[i + 1] - 1))
print(sum(m))

n = int(input())
u = list(map(int, input().split()))
for i in range(n - 2, -1, -1):
    if u[i] >= u[i + 1] and u[i] != 0:
        u[i] = u[i + 1] - 1
        if u[i + 1] == 0:
            u[i] = 0
    
print(sum(u))


''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import cProfile, math
from collections import Counter,defaultdict
from bisect import bisect_left,bisect,bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size
fac_warmup = False
printHeap = str()
memory_constrained = False
P = 10**9+7
import sys

class merge_find:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]
    def find(self,a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]
    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)
        if a==b:
            return
        if self.size[a]<self.size[b]:
            a,b = b,a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]
    def set_size(self, a):
        return self.size[self.find(a)]
    def __len__(self):
        return self.num_sets

def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")

def primeFactors(n): #n**0.5 complex 
    factors = dict()
    for i in range(2,math.ceil(math.sqrt(n))+1):  
        while n % i== 0: 
            if i in factors:
                factors[i]+=1
            else: factors[i]=1
            n = n // i 
    if n>2:
        factors[n]=1
    return (factors)

def fibonacci_modP(n,MOD):
    if n<2: return 1
    #print (n,MOD)
    return (cached_fn(fibonacci_modP, (n+1)//2, MOD)*cached_fn(fibonacci_modP, n//2, MOD) + cached_fn(fibonacci_modP, (n-1) // 2, MOD)*cached_fn(fibonacci_modP, (n-2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n , p): 
    if (p <= n): 
        return 0
    res = (p - 1) 
    for i in range (n + 1, p): 
        res = (res * cached_fn(InverseEuler,i, p)) % p 
    return res 

def binary(n,digits = 20):
    b = bin(n)[2:]
    b = '0'*(20-len(b))+b
    return b

def isprime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True
factorial_modP = []
def warm_up_fac(MOD):
    nonlocal factorial_modP,fac_warmup
    if fac_warmup: return
    factorial_modP= [1 for _ in range(fac_warmup_size+1)]
    for i in range(2,fac_warmup_size):
        factorial_modP[i]= (factorial_modP[i-1]*i) % MOD
    fac_warmup = True

def InverseEuler(n,MOD):
    return pow(n,MOD-2,MOD)

def nCr(n, r, MOD):
    nonlocal fac_warmup,factorial_modP
    if not fac_warmup:
        warm_up_fac(MOD)
        fac_warmup = True
    return (factorial_modP[n]*((pow(factorial_modP[r], MOD-2, MOD) * pow(factorial_modP[n-r], MOD-2, MOD)) % MOD)) % MOD

def test_print(*args):
    if testingMode:
        print(args)

def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")

def display_2D_list(li):
    for i in li:
        print(i)
def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm+=i
        res.append(sm)
    return res

def get_int():
    return int(stdin.readline().strip())

def get_tuple():
    return map(int, stdin.readline().split())

def get_list():
    return list(map(int, stdin.readline().split()))
import heapq,itertools
pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>' 
def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heapq.heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heapq.heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')
memory = dict()
def clear_cache():
    nonlocal memory
    memory = dict()
def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result

def ncr (n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
def binary_serach(i,li):
    #print("Search for ",i)
    fn = lambda x: li[x]-x//i
    x = -1
    b = len(li)
    while b>=1:
        #print(b,x)
        while b+x<len(li) and fn(b+x)>0: #Change this condition 2 to whatever you like
            x+=b
        b=b//2
    return x

# -------------------------------------------------------------- MAIN PROGRAM
TestCases = False
testingMode = False
fac_warmup_size = 10**5+100
optimiseForReccursion = True #Can not be used clubbed with TestCases
from math import factorial

def main():
    n = get_int()
    li = get_list()
    li.reverse()
    k = 1000000000000000
    res = 0
    for i in li:
        k = max(min(i,k-1),0)
        res+=k
    print(res)

    
# --------------------------------------------------------------------- END=


if TestCases: 
    for _ in range(get_int()): 
        cProfile.run('main()') if testingMode else main() 
else: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()

'''input
4
1 1 1 1
'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())

n=ri(1)
a=ri()
c=0
last=0
ans=0
ans=[a[-1]]
for i in range(n-2,-1,-1):
	ans.append(min(ans[-1]-1,a[i]))
for i in ans:
	if i>0:
		c+=i
print(c)

input()
S=list(map(int,input().split()))
an=S[-1]
la = S[-1]

for i in range(len(S) - 2, -1,-1):
    ne = max(min(la-1,S[i]), 0)
    an += ne
    la = ne
print(an)    

import sys
sys.setrecursionlimit(2000)
from collections import Counter
from functools import reduce
# sys.stdin.readline()

def __starting_point():

    # single variables
    n = [int(val) for val in sys.stdin.readline().split()][0]
    a = [int(val) for val in sys.stdin.readline().split()]


    prev = a[-1]
    count = prev
    for i in range(n-2, -1, -1):
        prev = min(a[i], prev-1)
        prev = max(prev, 0)
        count += prev

    print(count)       
 


__starting_point()

n = int(input())
a = [int(t) for t in input().split(' ')]

INF = 10**10

i = n-1
total = 0
mn = INF
while i >= 0:
    mn = max(0, min(mn - 1, a[i]))
    total += mn
    i -= 1

print(total)


'''stdin=open('input.txt')

def input():
	return stdin.readline()[:-1]'''

# a, b = map(int, input().split())

# l = list(map(int, input().split()))


# CODE BEGINS HERE.................

n = int(input())
a = list(map(int, input().split()))

a = a[::-1]

ans = a[0]
for i in range(1, n):
	if a[i] >= a[i - 1]:
		ans += max(a[i - 1] - 1, 0)
		a[i] = max(a[i - 1] - 1, 0)
	else:
		ans += a[i]

print(ans)
#CODE ENDS HERE....................




n=int(input())
a=list(map(int,input().split()))
summ=0
i=n-1
minn=a[i]
while i>=0:
    if minn>=a[i]:
        summ+=a[i]
        minn=a[i]-1
    else:
        summ+=minn
        minn=max(0,minn-1)
    i-=1
print(summ)

n = int(input())
a = list(map(int, input().split()))

a = a[::-1]

k = 0
mx = a[0] + 2

for c in a:
	mx = max(0, mx - 1)
	#print(k, c, mx)
	if c < mx:
		k += c
		mx = c
	
	elif mx == c:
		k += max(c, 0)
		mx = max(c, 0)
	
	else:
		k += mx

print(k)


n = int(input())
s = [int(i) for i  in input().split()]
s = s[::-1]
c = 100000000000
ans = 0
for i in s:
    if i < c:
        c = i
    else:
        c = max(c-1, 0)
    ans+=c
print(ans)