CodeEff/ECCO huggingface dataset:
# Original solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    if max(books) > mid:
        return False

    rem = mid
    while books:
        while rem >= books[0]:
            rem -= books[0]
            books = books[1:]
            if len(books) == 0:
                break
        rem = mid
        m -= 1

    if m >= 0:
        return True
    else:
        return False


def solve(m, n, books):
    ub = 1500000
    lb = 0
    min_width = float('inf')

    for i in range(100):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid

    return min_width



def main(args):
    while True:
        m, n = list(map(int, input().split()))
        if m == 0 and n == 0:
            break
        books = [int(eval(input())) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

# Optimized solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    if max(books) > mid:
        return False

    rem = mid
    while books:
        while rem >= books[0]:
            rem -= books[0]
            books = books[1:]
            if len(books) == 0:
                break
        rem = mid
        m -= 1

    if m >= 0:
        return True
    else:
        return False


def solve(m, n, books):
    ub = 1500000
    lb = 0
    min_width = float('inf')

    for i in range(50):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid

    return min_width



def main(args):
    while True:
        m, n = list(map(int, input().split()))
        if m == 0 and n == 0:
            break
        books = [int(eval(input())) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
a, b, c = input().split()
colors = 0
if a == b and b == c:
  colors = 1
elif a == b or b == c or c == a:
  colors = 2
else:
  colors = 3
print(colors)

# Optimized solution
s = set(input().split())
print((len(s)))
# Original solution
l=list(map(int,input().split()))
ls=[]
for i in l:
     ls.append(i)
k=set(ls)
print((len(k)))

# Optimized solution
a,b,c=input().split()

if a==b==c:
    print("1")
elif a==b or b==c or c==a:
    print("2")
else:
    print("3")
# Original solution
print((len(set(list(map(int,input().split()))))))

# Optimized solution
print((len(set(input().split()))))
# Original solution
l = [ int(x) for x in input().split() ]
l = set(l)
print((len(list(l))))


# Optimized solution
l = [ int(x) for x in input().split() ]
print((len(set(l))))
# Original solution
from collections import Counter
A,B,C = list(map(int,input().split()))
print((len(Counter([A,B,C]).most_common())))

# Optimized solution
A,B,C = list(map(int,input().split()))

print((len(set([A,B,C]))))
# Original solution
A,B,C = list(map(int,input().split()))

print((len(set([A,B,C]))))

# Optimized solution
# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
A,B,C = list(map(int,input().split()))

print((len({A,B,C})))
# Original solution
from collections import Counter
a = list(input().split())
print((len(Counter(a))))

# Optimized solution
a = list(map(int, input().split()))
print((len(set(a))))
# Original solution
import collections

p = [int(x) for x in input().split()]
c = collections.Counter(p)
print((len(c)))


# Optimized solution
p = [int(x) for x in input().split()]
print((len(set(p))))
# Original solution
a,b,c = list(map(int,input().split()))

if a == b == c:
  	print((1))
elif a == c or a == b or b == c:
  	print((2))
else:
  	print((3))

# Optimized solution
colors = list(map(int,input().split()))
print((len(set(colors))))
# Original solution
s = list(map(int, input().split()))

c = set(s)
print((len(c)))

# Optimized solution
p = list(map(int, input().split()))
print((len(set(p))))
# Original solution
a=list(map(int,input().split()))
s=set(a)
print((len(s)))


# Optimized solution
a=set(list(map(int,input().split())))
print((len(a)))
# Original solution
import collections

pen = list(map(str,input().split()))

print((len(collections.Counter(pen))))





# Optimized solution
a,b,c = list(map(int,input().split()))

if a == b == c:
    print((1))
elif a == b or b == c or c ==a:
    print((2))
else:
    print((3))
# Original solution
print((len(set([x for x in input().split()]))))

# Optimized solution
print((len(set(input().split()))))
# Original solution
a,b,c=list(map(int, input().split()))
if a==b and a==c:
    print((1))
elif a!=b and b!=c and c!=a:
    print((3))
else:
    print((2))

# Optimized solution
a,b,c=list(map(int, input().split()))
d={}
d[a]=1
d[b]=1
d[c]=1
print((len(d)))
# Original solution
a,b,c=list(map(int, input().split()))
d={}
d[a]=1
d[b]=1
d[c]=1
print((len(d)))

# Optimized solution
print((len(set(input().split()))))
# Original solution
m=998244353
M=1<<20
f=[0]*M
g=[0]*M
h=[0]*M
f[0]=g[0]=f[1]=g[1]=h[1]=1
for i in range(2,M):
	f[i]=f[i-1]*i%m
	h[i]=m-h[m%i]*(m//i)%m
	g[i]=g[i-1]*h[i]%m
A,B=list(map(int,input().split()))
if A<B:A,B=B,A
a=0
b=1
for j in range(1,B+1):
	a+=b*f[A+B-j]*g[B-j]*g[A]
	b=b*2%m
print(((a*f[A]*f[B]*g[A+B]+A)%m))

# Optimized solution
m=998244353
M=1<<20
f=[1]*M
g=[1]*M
h=[1]*M
h[0]=0
for i in range(2,M):
	f[i]=f[i-1]*i%m
	h[i]=m-h[m%i]*(m//i)%m
	g[i]=g[i-1]*h[i]%m
A,B=list(map(int,input().split()))
if A<B:A,B=B,A
a=0
b=1
for j in range(1,B+1):
	a+=b*f[A+B-j]*g[B-j]*g[A]
	b=b*2%m
print(((a*f[A]*f[B]*g[A+B]+A)%m))
# Original solution
M=8**7
m,f,g,i,a,b=M*476+1,[1],[1]*M,1,0,1
while i<M:f+=f[-1]*i%m,;i+=1
g[-1]=pow(f[-1],m-2,m)
while i>1:i-=1;g[i-1]=g[i]*i%m
A,B=list(map(int,input().split()))
if A<B:A,B=B,A
while i<=B:a+=b*f[A+B-i]*g[B-i];b=b*2%m;i+=1
print(((a*f[B]*g[A+B]+A)%m))

# Optimized solution
M=8**7
m,f,g,i=M*476+1,[j:=1],[k:=1]*M,1
while i<M:f+=f[-1]*i%m,;i+=1
g+=pow(M*f[-1],m-2,m),
while i:g[i-1]=g[i]*i%m;i-=1
A,B=list(map(int,input().split()))
if A<B:A,B=B,A
while j<=B:i+=k*f[A+B-j]*g[B-j];k=k*2%m;j+=1
print(((i*f[B]*g[A+B]+A)%m))
# Original solution
while True:
    n = int(eval(input()))
    if n == 0:
        break
    z = sorted([tuple(map(int, input().split())) for _ in range(n)],  key=lambda x: x[1])
    cnt = total = 0
    for a, b in z:
        total += a
        if total > b:
            break
        cnt += 1
    print(("Yes" if cnt == n else "No"))

# Optimized solution
while True:
    n = int(eval(input()))
    if n == 0:
        break
    z = sorted([tuple(map(int, input().split())) for _ in range(n)],  key=lambda x: x[1])
    cnt = total = 0
    for a, b in z:
        total += a
        if total > b:
            cnt = 1
            break
    print(("No" if cnt else "Yes"))
# Original solution
while 1:
	n = int(input())
	if n == 0:
		break
	bridge = [0 for i in range(n)]
	gold = [0 for i in range(n)]
	for i in range(n):
		gold[i], bridge[i] = list(map(int,input().split(" ")))
	dp = {0:0}
	for i in range(n):
		tmp_dp = dict()
		for k,v in dp.items():
			for j in range(n):
				bit = 1 << j
				if (k & bit != 0) or (k|bit in tmp_dp):
					continue
				if v + gold[j] <= bridge[j]:
					tmp_dp[k|bit] = v + gold[j]
		dp = tmp_dp
	print("Yes" if (2**n - 1) in dp else "No")

# Optimized solution
while 1:
	n = int(input())
	if n == 0:
		break
	land = [list(map(int,input().split(" "))) for i in range(n)]
	land.sort(key = lambda x:(x[1],x[0]))
	gold = 0
	for i in range(n):
		gold += land[i][0]
		if gold > land[i][1]:
			print("No")
			break
	else:
		print("Yes")
# Original solution
import sys
C = sys.stdin.readlines()
print((C[0][0]+C[1][1]+C[2][2]))

# Optimized solution
print((input()[0]+input()[1]+input()[2]))
# Original solution
l = [0] * 3
for i in range(3):
    l[i] = list(input())

for i in range(3):
    for j in range(3):
        if i == j:
            print(l[i][j], end='')
print("")


# Optimized solution
for i in range(3):
    print(input()[i], end='')
print()
# Original solution
a=input()[0]
b=input()[1]
c=input()[2]
print((a+b+c))

# Optimized solution
a,b,c=[input()[i] for i in range(3)]
print((a+b+c))
# Original solution
print((''.join(input()[i]for i in range(3))))

# Optimized solution
print((open(0).read()[::5]))
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

if A[0] != 0:
    print((-1))
    exit()

ans = 0
tmp = 0
for num in reversed(A):
    if tmp > 0:
        if num == tmp-1:
            tmp = num
        elif num >= tmp:
            ans += num
            tmp = num
        elif num < tmp-1:
            print((-1))
            exit()

    else:
        ans += num
        tmp = num
        

print(ans)

# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

#先頭は増やせないから０以外なら終わり
if A[0] != 0:
    print((-1))
    exit()


ans = 0
prev = 0
for n in reversed(A):
    if prev != 0:
        # 後ろから見て１ずつ減少する場合
        if n == prev - 1:
            prev = n
        # 前以上のとき、新たにその数字のために階段を構成する（前の数字を作る仮定で作れない）ので、その分の操作数が必要
        elif n >= prev:
            ans += n
            prev = n
        # ２以上の差があると作れない
        else:
            print((-1))
            exit()
    else:
        ans += n
        prev = n


print(ans)
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]

if A[0] != 0:
    print((-1))
    exit()

for i in range(N - 1):
    if A[i] < A[i + 1] and A[i + 1] - A[i] != 1:
        print((-1))
        exit()
    if A[i] > i + 1:
        print((-1))
        exit()

ans = 0
i = 1
old = 0
while i != N:
    if A[i] <= old:
        ans += old
    old = A[i]
    i += 1

print((ans + A[-1]))


# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]

if A[0] != 0:
    print((-1))
    exit()

for i in range(N - 1):
    if A[i] < A[i + 1] and A[i + 1] - A[i] != 1:
        print((-1))
        exit()
    if A[i] > i + 1:
        print((-1))
        exit()

ans = 0
for i in range(1, N):
    if A[i-1] >= A[i]:
        ans += A[i-1]
print((ans + A[-1]))
# Original solution
# AGC024C - Sequence Growing Easy
def main():
    N, *A = list(map(int, open(0)))
    A.append(0)
    if A[0]:  # corner case
        print((-1))
        return
    ans = 0
    for i, j in zip(A[::-1], A[::-1][1:]):
        if i > j + 1:
            print((-1))
            return
        if j >= i:
            ans += j
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# AGC024C - Sequence Growing Easy
def main():
    N, *A = list(map(int, open(0)))
    if A[0]:  # can't increment A_0
        print((-1))
        return
    A.append(0)
    ans, B = 0, A[::-1]
    for i, j in zip(B, B[1:]):  # check from the last
        if i > j + 1:  # increment from left one must be 0 or 1
            print((-1))
            return
        if j >= i:  # left one is an end of subsequence
            ans += j
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import heapq


class Value:
    def __init__(self, val, f):
        self.val = val
        self.key = f(val)

    def __lt__(self, other):
        return self.key < other.key

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, f=lambda x: x):
        for i in range(len(arr)):
            arr[i] = Value(arr[i], f)
        self.func = f
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq).val

    def push(self, a):
        heapq.heappush(self.hq, Value(a, self.func))

    def top(self):
        return self.hq[0].val


n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
if a[0] > 0:
    print((-1))
    exit(0)
hq = Heapq([], f=lambda x: (-a[x], x))
for i, x in enumerate(a):
    if x > 0:
        hq.push(i)
ans = 0
while hq.hq:
    i = hq.pop()
    if a[i] - 1 == a[i - 1]:
        ans += 1
        a[i] = (a[i + 1] - 1 if i != n - 1 else 0)
        if a[i] > 0:
            hq.push(i)
    else:
        print((-1))
        exit(0)
print(ans)


# Optimized solution
n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)] + [0]
if a[0] > 0:
    print((-1))
else:
    ans = 0
    for i in range(n):
        if a[i] < a[i + 1] - 1:
            print((-1))
            break
        elif a[i] >= a[i + 1]:
            ans += a[i]
    else:
        print(ans)
# Original solution
N = int(eval(input()))
A = [0]*N
for i in range(N):
    A[i] = int(eval(input()))

B = [0]*N
possible = True
tot = 0
for i in range(N):
    if A[-(i+1)] > N-i-1:
        possible = False
        break
    elif B[-(i+1)] > A[-(i+1)]:
        possible = False
        break
    elif B[-(i+1)] == A[-(i+1)]:
        continue
    else:
        if i == 0:
            B[-(i+1+A[-(i+1)]):] = list(range(A[-(i+1)]+1))
            tot += A[-(i+1)]
        else:
            B[-(i+1+A[-(i+1)]):-i] = list(range(A[-(i+1)]+1))
            tot += A[-(i+1)]
if not possible:
    print((-1))
else:
    print(tot)

# Optimized solution
N = int(eval(input()))
A = [0]*N
for i in range(N):
    A[i] = int(eval(input()))

B = [0]*N
possible = True
tot = 0
if A[0] == 0:
    for i in range(N-1):
        if A[-(i+1)] > N-i-1:
            possible = False
            break
        elif B[-(i+1)] > A[-(i+1)]:
            possible = False
            break
        elif B[-(i+1)] == A[-(i+1)]:
            B[-(i+2)] = A[-(i+1)]-1
            continue
        else:
            B[-(i+2)] = A[-(i+1)]-1
            tot += A[-(i+1)]
    if not possible:
        print((-1))
    else:
        print(tot)
else:
    print((-1))
# Original solution
n=int(eval(input()))
l=[int(eval(input())) for _ in range(n)]
ans=0
if l[0]!=0:
  print((-1))
  exit()
for i in range(n-1):
  if l[i+1]-l[i]>1:
    print((-1))
    exit()
  elif (l[i]+1==l[i+1]):
    ans+=1
  else:
    ans+=l[i+1]
print(ans)


# Optimized solution
n=int(eval(input()))
l=[int(eval(input())) for _ in range(n)]
ans=0
if l[0]!=0:
  print((-1))
  exit()
for i in range(n-1):
  if (l[i]+1==l[i+1]):
    ans+=1
  elif (l[i]>=l[i+1]):
    ans+=l[i+1]
  else:
    print((-1))
    exit()
print(ans)
# Original solution
#!/usr/bin/env python3
#AGC24 C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
if a[0] != 0:
    print((-1))
    quit()
for i in range(1,n):
    if a[i] - a[i-1] > 1:
        print((-1))
        quit()
ans = 0
for i in range(1,n):
    if a[i] == a[i-1] and a[i] > 0:
        ans += a[i]
    elif a[i] == a[i-1] + 1:
        ans += 1
    elif a[i] < a[i-1]:
        ans += a[i]
print(ans)


# Optimized solution
#!/usr/bin/env python3
#AGC24 C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
if a[0] != 0:
    print((-1))
    quit()
for i in range(1,n):
    if a[i] - a[i-1] > 1:
        print((-1))
        quit()
ans = 0
for i in range(1,n):
    if a[i] <= a[i-1]:
        ans += a[i]
        continue
    if a[i] == a[i-1] + 1:
        ans += 1
        continue
print(ans)
# Original solution
N = int( eval(input()))
A = [ int( eval(input())) for _ in range(N)]
now = 0
ans = 0
if A[0] != 0:
    ans = -1
else:
   for i in range(1,N):
       if A[i] > i:
           ans = -1
           break
       elif now + 1 == A[i]:
           ans += 1
           now += 1
       elif now >= A[i]:
           ans += A[i]
           now = A[i]
       else:
           ans = -1
           break
print(ans)

# Optimized solution
N = int( eval(input()))
A = [ int( eval(input())) for _ in range(N)]
now = 0
ans = 0
if A[0] != 0:
    ans = -1
else:
   for i in range(1,N):
       a = A[i]
       if a > i:
           ans = -1
           break
       elif now + 1 == a:
           ans += 1
           now += 1
       elif now >= a:
           ans += a
           now = a
       else:
           ans = -1
           break
print(ans)
# Original solution
N = int( eval(input()))
A = [ int( eval(input())) for _ in range(N)]
now = 0
ans = 0
if A[0] != 0:
    ans = -1
else:
   for i in range(1,N):
       # if A[i] > i:
       #     ans = -1
       #     break
       if now + 1 == A[i]:
           ans += 1
           now += 1
       elif now >= A[i]:
           ans += A[i]
           now = A[i]
       else:
           ans = -1
           break
print(ans)

# Optimized solution
N = int( eval(input()))
A = [ int( eval(input())) for _ in range(N)]
now = 0
ans = 0
if A[0] != 0:
    ans = -1
else:
   for i in range(1,N):
       a = A[i]
       # if a > i:
       #     ans = -1
       #     break
       #el
       if now + 1 == a:
           ans += 1
           now += 1
       elif now >= a:
           ans += a
           now = a
       else:
           ans = -1
           break
print(ans)
# Original solution
n = int(eval(input()))
a = []
for i in range(n):
    a.append(int(eval(input())))

flag = True
for i in range(n - 1):
    if a[i + 1] - a[i] >= 2:
        flag = False
if a[0] != 0:
    flag = False

count = 0
start = 0
if flag == True:
    while a != [0] * n:
        for i in range(start, n - 1):
            if a[i] + 1 == a[i + 1]:
                start = i
                break
        for j in range(start, n - 1):
            if a[j] + 1 != a[j + 1]:
                end = j
                break
            if j == n - 2:
                end = n - 1
        for k in range(end, start - 1, -1):
            if end != n - 1:
                a[k] = max(0, a[k + 1] - 1)
            else:
                a[k] = 0
        count = count + end - start
if flag == False:
    print((-1))
else:
    print(count)

# Optimized solution
n = int(eval(input()))
a = []
for i in range(n):
    a.append(int(eval(input())))

flag = True
for i in range(n - 1):
    if a[i + 1] - a[i] >= 2:
        flag = False
if a[0] != 0:
    flag = False

count = 0
if flag == True:
    for i in range(n - 1):
        if a[i] != 0:
            count = count + 1
        if a[i] >= a[i + 1]:
            count = count + max(0, a[i + 1] - 1)
   
if flag == False:
    print((-1))
elif a[n - 1] != 0:
    print((count + 1))
else:
    print(count)
# Original solution
n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]

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


# Optimized solution
n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]

ans, tmp = 0, 0
for i in range(n - 1, 0, -1):
    if a[i] - a[i - 1] > 1:
        print((-1))
        break
    if tmp != a[i]:
        ans += a[i]
    tmp = max(a[i] - 1, 0)
else:
    print((-1 if a[0] > 0 else ans))
# Original solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

tmp = 0
cnt = 0
for i in range(N-1, -1, -1):
	tmp -= 1
	if i < A[i]:
		print((-1))
		exit()
	elif A[i] < tmp:
		print((-1))
		exit()
	elif tmp < A[i]:
		cnt += A[i]
		tmp = A[i]

print(cnt)


# Optimized solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

ans = 0
tmp = A[0]
for i, a in enumerate(A):
	if i < a or tmp+1 < a:
		print((-1))
		break
	if a != tmp+1:
		ans += tmp
	tmp = a

else:
	ans += tmp
	print(ans)
# Original solution
N = int(eval(input()))
A = [[]]

for _ in range(N):
    a = int(eval(input()))
    if len(A[-1]) > 0 and a < A[-1][-1]:
        A.append([])
    A[-1].append(a)

def isOk():
    for l, r in zip(A, A[1:]):
        if l[-1] + 1 < r[0]:
            return False
    for grp in A:
        for l, r in zip(grp, grp[1:]):
            if l + 1 < r:
                return False

    return A[0][0] == 0

if not isOk():
    print((-1))
    exit()

B = []
for a in A:
    B.extend(a)
B = [-10**18] + B[::-1]

ans = 0
for r, l in zip(B, B[1:]):
    if l >= r:
        ans += l
print(ans)


# Optimized solution
import sys
input = sys.stdin.buffer.readline

N = int(eval(input()))
G = [[]]
A = []

for _ in range(N):
    a = int(eval(input()))
    if len(G[-1]) > 0 and G[-1][-1] > a:
        G.append([])
    A.append(a)
    G[-1].append(a)

def isOk():
    if any(l[-1] + 1 < r[0] for l, r in zip(G, G[1:])):
        return False
    for grp in G:
        if any(l + 1 < r for l, r in zip(grp, grp[1:])):
            return False
    return A[0] == 0

if not isOk():
    print((-1))
    exit()

ans = 0
A = [-10**18] + A[::-1]

for r, l in zip(A, A[1:]):
    if l >= r:
        ans += l
print(ans)
# Original solution
n = int(eval(input()))
a = [int(eval(input())) for _i in range(n)] + [-1]

result = -1
for i in range(n):
    if a[i-1] >= a[i]:
        result += a[i]
    elif a[i-1] + 1 == a[i]:
        result += 1
    else:
        result = -1
        break
print(result)

# Optimized solution
n,r=int(eval(input())),-1
a = [int(eval(input())) for _i in range(n)]+[-1]
for i in range(n):
    if a[i-1] >= a[i]:r+=a[i]
    elif a[i-1]+1==a[i]:r+=1
    else:r=-1;break
print(r)