Problem:
 Score : 700 points    Problem Statement There is a sequence X of length N , where every element is initially 0 . Let X_i denote the i -th element of X .  You are given a sequence A of length N . The i -th element of A is A_i . Determine if we can make X equal to A by repeating the operation below. If we can, find the minimum number of operations required.   Choose an integer i such that 1\leq i\leq N-1 . Replace the value of X_{i+1} with the value of X_i plus 1 .       Constraints  1 \leq N \leq 2 \times 10^5  0 \leq A_i \leq 10^9(1\leq i\leq N)  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  :  A_N       Output If we can make X equal to A by repeating the operation, print the minimum number of operations required. If we cannot, print -1 .        Sample Input 1 4
0
1
1
2      Sample Output 1 3  We can make X equal to A as follows:   Choose i=2 . X becomes (0,0,1,0) .  Choose i=1 . X becomes (0,1,1,0) .  Choose i=3 . X becomes (0,1,1,2) .        Sample Input 2 3
1
2
1      Sample Output 2 -1       Sample Input 3 9
0
1
1
0
1
2
2
1
2      Sample Output 3 8

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


def main():
    n = int(input())
    a = [None] * n
    for i in range(n):
        a[i] = int(input())

    prev = a[-1]
    if a[0]!=0:
        print(-1)
        return
    count = 0
    for num in a[::-1]:
        if prev==num+1:
            pass
        elif prev >= num+2:
            print(-1)
            return
        else:
            count += num
        prev = num
    print(count)
main()

Solution (Python):
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

def main():
    cur = 0
    ans = 0

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

    for a in A:
        if a <= cur:
            ans += a
        elif a == cur+1:
            ans += 1
        else:
            print(-1)
            return
        cur = a

    print(ans)

    
main()

Solution (Python):
n = int(input())
ai = [int(input()) for i in range(n)]

tmp = ai[n-1]
ans = 0
ren = 0

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

for i in range(1,n):
    if tmp - 1 > ai[n-i-1]:
        print(-1)
        exit()
    
    if tmp - 1 == ai[n-i-1]:
        tmp -= 1
        ren += 1
        
    else:
        ans += ai[n-i]
        ans += ren
        
        tmp = ai[n-i-1]
        ren = 0

ans += ai[0]
ans += ren
    
print(ans)

Solution (Python):
n = int(input())
lis = [int(input()) for i in range(n)]
if lis[0] != 0:print(-1);exit()
ans = 0
for i in range(n-1,0,-1):
    if lis[i] - lis[i-1] > 1:print(-1);exit()
    elif lis[i] - lis[i-1] == 1:ans += 1
    else:ans += lis[i]
print(ans)

Solution (Python):
n = int(input())
lis = [int(input()) for i in range(n)]
if lis[0] != 0:print(-1);exit()
ans = 0
for i in range(n-1,0,-1):
    if lis[i] - lis[i-1] > 1:print(-1);exit()
    elif lis[i] - lis[i-1] == 1:ans += 1
    else:ans += lis[i]
print(ans)

Solution (Python):
n = int(input())
a = [int(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)

Solution (Python):
N=int(input())
pre=0
ans=0
for i in range(N):
    a=int(input())
    if i==0 and a!=0:
        print(-1)
        exit()
    if i>0:
        if pre+1<a:
            print(-1)
            exit()
        if a==pre+1:
            ans+=1
        elif pre>=a:
            ans+=a
    pre=a
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = [int(readline()) for _ in range(n)]
if a[0] != 0:
    print(-1)
    exit()
ans = 0
for ab, af in zip(a, a[1:]):
    if af - ab > 1:
        print(-1)
        exit()
    if ab >= af:
        ans += af
    else:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
A = [int(input()) for i in range(n)]

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

for i in range(1, n):
    if A[i] > A[i-1]+1:
        print(-1)
        exit()

ans = 0
for i in reversed(range(1, n)):
    if A[i-1] == A[i]-1:
        ans += 1
    else:
        ans += A[i]

print(ans)

Solution (Python):
n = int(input())
A = [int(input()) for i in range(n)]

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

for i in range(1, n):
    if A[i] > A[i-1]+1:
        print(-1)
        exit()

ans = 0
for i in reversed(range(1, n)):
    if A[i-1] == A[i]-1:
        ans += 1
    else:
        ans += A[i]

print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
if a[0] != 0:
    print(-1)
    exit()

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

Solution (Python):
N = int(input())
A = [-1] + [int(input()) for _ in range(N)]

count = -1
for i in range(N, 0, -1):
    if A[i] - 1 > A[i - 1]:
        print (-1)
        exit()
    elif A[i] - 1 == A[i - 1]:
        count += 1
    else:
        count += A[i]

print (count)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    A=[int(input()) for _ in range(N)]

    if A[0]!=0:
        print(-1)
        exit()
    ans=0
    d=0
    for i in range(1,N):
        if A[i]==0: continue
        if A[i]>d+1:
            print(-1)
            exit()
        d=A[i]
        if A[i]==A[i-1]+1:
            ans+=1
        else:
            ans+=A[i]

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=[int(input())for _ in range(n)]
if a[0]!=0:print(-1);exit()
for i in range(1,n):
  if a[i-1]+1<a[i]:print(-1);exit()
ans=0
for i in range(n-1,0,-1):
  if a[i]<=a[i-1]:ans+=a[i]
  else:ans+=1
print(ans)

Solution (Python):
N = int(input())
A = [[]]

for _ in range(N):
    a = int(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)

Solution (Python):







N = int(input())
cur = 0
ans = 0
for i in range(N):
  a = int(input())
  if i == 0 and a != 0:
    print(-1)
    exit(0)
  elif a == 0:
    ans += 0
  elif a == cur + 1:
    ans += 1
  elif a <= cur:
    ans += a
  else:
    print(-1)
    exit(0)
  cur = a
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = IR(n)
if A[0]:
    print(-1)
    exit()
ret = 0
ans = 0
for i in range(1, n):
    if A[i] > ret + 1:
        print(-1)
        exit()
    elif A[i] == ret + 1:
        ans += 1
    else:
        ans += A[i]
    ret = A[i]
print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b

def main():
    N = int(readline())
    A = [int(readline()) for i in range(N)]
    prev = 0
    count = 0
    flag = True
    for i in range(N):
        if A[i]>prev:
            flag = False
            break
        elif A[i]==prev:
            prev+=1
            if prev!=1:
                count += 1
        else:
            prev = A[i]+1
            count += A[i]
    if flag:
        print(count)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
key = [0]*n
flag = True
ans = 0
for i in range(n):
  a = int(input())
  if i == 0:
    if a != 0:
      flag = False
      break
    continue
  if a > key[i-1]+1:
    flag = False
    break
  key[i] = a
  if a == 1:
    ans += 1
  elif a == key[i-1]+1:
    ans += 1
  else:
    ans += a
if flag:
  print(ans)
else:
  print(-1)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]

    if a[0] != 0:
        print(-1)
        return
    
    ans = a[-1]
    down = a[-1]
    stair = a[-1]
    for i in range(n - 2,-1,-1):
        down -= 1
        stair -= 1
        if down > a[i]:
            print(-1)
            return
        if stair == a[i]:
            continue
        down = max(down,a[i])
        stair = a[i]
        ans += stair
    
    print(ans)

if __name__ =='__main__':
    main()

Solution (Python):
N=int(input())
A=[]
for i in range(0,N):
    A.append(int(input()))

ans=0
for i in range(0,N-1):
    if A[i]>i:
        print(-1)
        break
    else:
        if A[i+1]>A[i]:
            if A[i+1]-A[i]>=2:
                print(-1)
                break
        else:
            ans+=A[i]
else:

    if A[N-1]>N-1:
        print(-1)
    else:
        ans+=A[-1]
        print(ans)

Solution (Python):
import math
N = int( input())
As  = [int(input())for _ in  range(N)]
ans = 0
for i in range(N):
    if As[i] > i or As[i] - As[i - 1] > 1:
        ans = -1
        break

    else:
        if As[i] == As[i -1] + 1:
            ans += 1
        else:
            ans += As[i]

print(ans)

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
if A[0]!=0:
  print(-1)
  exit()
ans=0
for i in range(N-1):
  if A[i+1]-A[i]>1:
    print(-1)
    exit()
  elif A[i+1]-A[i]==1:
    ans+=1
  else:
    ans+=A[i+1]
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n = II()
    a = IR(n)
    if a[0] != 0:
        print(-1)
        return
    ans = 0
    tmp = 0
    for i in a:
        if tmp + 1 == i:
            tmp += 1
            continue
        if tmp >= i:
            ans += tmp
            tmp = i
        else:
            print(-1)
            return
    print(ans + tmp)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
A = [int(input()) for _ in range(n)]
ans = 0
prev = 0
if A[0]!=0:
  print(-1)
  exit()
for i in range(n):
    a = A[i]
    if prev == None and a!=0:
        ans = -1
        break
    if prev != None:
        dif = a-prev
        if dif >= 2:
            ans = -1
            break
        elif dif<=0:
            ans += prev
    prev = a
if ans!=-1:
    ans += prev
print(ans)

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
A=[int(input()) for i in range(N)]
if A[0]>0:
    print(-1)
    exit()
for i in range(N-1):
    if A[i]+1<A[i+1]:
        print(-1)
        exit()



count=A[-1]
for i in range(1,N)[::-1]:

    if A[i-1]==A[i]-1:
        pass
    else:
        count+=A[i-1]
print(count)

Solution (Python):
n=int(input())
a=[int(input())for _ in range(n)]
a=a[::-1]
cnt=0
ans=0
for i in range(n):
	if cnt==0:
		if a[i]!=0:
			cnt=a[i]
			ans+=a[i]
	else:
		cnt-=1
		if a[i]>cnt:
			cnt=a[i]
			ans+=a[i]
		elif a[i]<cnt:
			print(-1)
			exit()
if cnt:
	print(-1)
	exit()
print(ans)

Solution (Python):
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
    if i == 0:
        if a[0] != 0:
            print("-1")
            exit()
    else:
        if a[i] >= a[i-1]+2:
            print("-1")
            exit()
a += [a[-1]]
a.reverse()

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

Solution (Python):
n = int(input())

ans = -1

tmp = -1

for _ in range(n):
  a = int(input())
  if a == tmp +1:
    ans += 1
    tmp = a
  elif a <= tmp:
    ans += a
    tmp = a
  else:
    print(-1)
    exit()

print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]

ans = 0

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [INT() for _ in range(N)]
ans = 0
tmp = A[0]
for i, a in enumerate(A):
	if a > i or a >= tmp+2:
		print(-1)
		break
	if a != tmp+1:
		ans += tmp
	tmp = a

else:
	ans += tmp
	print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
if 0 < A[0]:
    print(-1)
    exit()
ans = 0
for i in range(1, N):
    if 1 < A[i] - A[i - 1]:
        print(-1)
        exit()
    elif A[i] - A[i - 1] == 1:
        ans += 1
    elif A[i] == A[i - 1]:
        ans += A[i]
    else:
        ans += A[i]
print(ans)

Solution (Python):
flag = True
n = int(input())
L = []
for i in range(n):
    t = int(input())
    L.append(t)
L.append(0)
if L[0] != 0:
    flag = False
cur = 0
ans = 0
for i in range(1, n+1):
    if cur < L[i]:
        if L[i]-cur != 1:
            flag = False
            break
        else:
            ans += 1
            cur = L[i]
    else:
        ans += L[i]
        cur = L[i]
if flag:
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
l=[int(input()) for i in range(n)]
if l[0]!=0:
    print(-1)
    quit()
l.reverse()
l+=[0]
ans=0
i=0
while i<n-1:
    if l[i]>n-i-1:
        print(-1)
        quit()
    if l[i+1]+1==l[i]:
        ans+=l[i]
        while l[i+1]+1==l[i]:
            i+=1
        i+=1
    elif l[i+1]+1<l[i]:
        print(-1)
        quit()
    else:
        ans+=l[i]
        i+=1
print(ans)

Solution (Python):


from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


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


def II():
    return int(input())




N = int(input())
A = []
for i in range(N):
    A.append(II())


if A[0] >0:
    print(-1)
    sys.exit()

for i in range(1, N):
    if A[i]-A[i-1] > 1:
        print(-1)
        sys.exit()

count = 0
x = [0]*N

for i in range(0,N-1):
    if A[i]+1==A[i+1]:
        count+=1
    else:
        count+=A[i+1]

""" for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1

 """
print(count)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
ans = 0
if A[0] != 0:
    ans = -1
else:
    for i in range(1, N)[::-1]:
        d = A[i] - A[i-1]
        if d > 1:
            ans = -1
            break
        if d == 1:
            ans += 1
        else:
            ans += A[i]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


def inv(a, mod):
    return pow(a, mod - 2, mod)


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    if A[0] != 0:
        print(-1)
        return
    
    for i in range(N - 1):
        if A[i + 1] - A[i] > 1:
            print(-1)
            return
    
    res = 0
    c = 0
    for a in A[::-1]:
        if c < a:
            res += a
            c = a
        c -= 1
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
for i in range(n-1,-1,-1):
    if i == 0:
        if a[i] != 0:
            print(-1)
            exit()
    else:
        if a[i-1] + 1 < a[i]:
            print(-1)
            exit()
        elif a[i-1] + 1 == a[i]:
            ans += 1
        else:
            ans += a[i]
print(ans)

Solution (Python):


N=int(input())

pre=int(input())
if pre!=0:
    print(-1)
    exit()

ans=0
count=0
for _ in range(N-1):
    A=int(input())
    if A-pre>1:
        print(-1)
        exit()
    if A==pre:
        count+=1
    else:
        ans+=pre*count
        if A<pre:
            ans+=(A-1)
        ans+=1
        count=0
        
    pre=A

print(ans+pre*count)

Solution (Python):
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    ans = 0
    pre = 0
    for a in A[::-1]:
        if a >= pre:
            ans += a
        elif a+2 <= pre:
            return print(-1)
        pre = a
    if A[0] != 0:
        return print(-1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())

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

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

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
if A[0]:
    print(-1)
    exit()

ans = 0
for a,b in zip(A,A[1:]):
    if b-a > 1:
        print(-1)
        exit()
    if b==0: continue
    if b-a == 1:
        ans += 1
    else:
        ans += b
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def calc(l):
    l2 = l[::-1]
    res = l2[0]
    
    for i in range(1, len(l2)):
        if l2[i-1]-1>l2[i]:
            print(-1)
            exit()
            
        if l2[i]!=l2[i-1]-1:
            res += l2[i]

    return res

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    if A[i]>i:
        print(-1)
        exit()

ans = 0
l = []

for i in range(N):
    if i==N-1 or A[i]>A[i+1]:
        l.append(A[i])
        ans += calc(l)
        l = []
    else:
        l.append(A[i])

print(ans)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    if A[0] > 0: print(-1)
    else:
        count = 0
        for i in range(1, N):
            a = A[i]
            if a <= A[i-1]: count += a
            elif a > A[i-1]:
                if a == A[i-1] + 1: count += 1
                else: 
                    print(-1)
                    break
        else: print(count)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LIN(N)
    for i,a in enumerate(A):
        if i<a:
            print(-1)
            return
    now_lim = 0
    ans = 0
    for i in range(N)[::-1]:
        now_lim-=1
        now_lim = max(0, now_lim)
        if A[i]<now_lim:
            print(-1)
            return
        elif A[i] == now_lim:
            pass
        else:
            ans += A[i]
        now_lim = max(A[i],now_lim)
    print(ans)
        
if __name__ == '__main__':
    main()

Solution (Python):
def ng():
    print(-1)
    exit()

def main():
    N,*P=map(int, open(0).read().split())
    ans=0
    pre=0
    if P[0]!=0: ng()
    for p in P[1:]:
        if pre+1<p: ng()
        ans+=1 if pre+1==p else p
        pre=p
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)][::-1]

if A[-1]:
    print(-1)
else:
    bef = A[0]
    c, ans = 0, 0
    for i in A:
        if bef!=i:
            if bef-i > 1:
                ans = -1
                break
            ans += bef*c
            c = 1 if bef<i else 0
        else:
            c += 1
        bef = i
    print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)][::-1]

if A[-1] != 0:
    print(-1)
else:
    bef = A[0]
    c, ans = 0, 0
    for i in A:
        if bef!=i:
            if bef-i > 1:
                print(-1)
                break
            ans += bef*c
            c = 1 if bef<i else 0
        else:
            c += 1
        bef = i
    else:
        print(ans)

Solution (Python):
from itertools import accumulate

N = int(input())
A = [int(input()) for _ in range(N)]

if A[0] != 0:
    print(-1)
else:
    A.reverse()
    bef = A[0]
    c = 0
    ans = 0
    for i in A:
        if bef!=i:
            if bef-i > 1:
                print(-1)
                break
            ans += bef*c
            c = 1 if bef<i else 0
        else:
            c += 1
        bef = i
    else:
        print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 0
if A[0] != 0:
    print(-1)
    exit()

for i in range(1, N):
    if A[i] - A[i-1] > 1:  
        print(-1)
        exit()

now = A[0]
for i in range(1, N):
    if A[i] == now+1:
        ans += 1
        now = A[i]
    else:
        ans += A[i]
        now = A[i]
print(ans)

Solution (Python):
import sys
read = sys.stdin.read

n = int(input())
A = list(map(int, read().split()))
if A[0] != 0:
  print(-1)
else:
  ans = 0
  A += [0]
  for i in range(n):
    if A[i+1] - A[i] > 1:
      print(-1)
      exit()
    if A[i]+1 != A[i+1]:
      ans += A[i]
  print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
        
x = 0
ans = 0
for i in range(N-1, -1, -1):
    if A[i] > x:
        ans += A[i]
        x = A[i]
    elif x > A[i]:
        ans = -1
        break
    x -= 1
if A[0] > 0:
    ans = -1    
print(ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append(inn())
    if len(a)>=2 and a[-1]>a[-2]+1:
        print(-1)
        exit()
if a[0]!=0:
    print(-1)
    exit()
cnt = 0
for i in range(1,n):
    if i==n-1:
        cnt += a[n-1]
    if a[i]!=a[i-1]+1:
        cnt += a[i-1]
print(cnt)

Solution (Python):


n = int(input())

nums = [int(input()) for i in range(n)]

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

ans = 0
for i in range(1, n):
    if nums[i] > nums[i-1] + 1:
        print(-1)
        exit()
    elif nums[i] == nums[i-1] + 1:
        
        ans += 1
    else:
        
        ans += nums[i]

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N = I()
A = MI(N,1)

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

ans = 0
for i in range(1,N):
    if A[i]-A[i-1] >= 2:
        print(-1)
        exit()
    else:
        if A[i]-A[i-1] == 1:
            ans += 1
        else:
            ans += A[i]

print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import numpy as np
N = int(input())
A = np.array([int(input()) for _ in range(N)] + [0], dtype=np.int64)

ans = (A[:-1][A[:-1] >= A[1:]]).sum()
if any(A[:-1] + 1 < A[1:]):
    ans = -1
elif A[0] != 0:
    ans = -1

print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LIN(N)
    for i,a in enumerate(A):
        if i<a:
            print(-1)
            return
    now_lim = 0
    ans = 0
    for i in range(N)[::-1]:
        now_lim-=1
        now_lim = max(0, now_lim)
        
        if A[i]<now_lim:
            print(-1)
            return
        elif A[i] == now_lim:
            pass
        else:
            ans += A[i]
        now_lim = max(A[i],now_lim)
        
    print(ans)
        
if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
x=[0]*(n+1)
a=[int(input()) for _ in range(n)]
if a[0]!=0:
  print(-1)
  exit()
for i in range(1,n):
  if a[i]-a[i-1]>1:
    print(-1)
    exit()
res=0
for i in range(1,n):
  if a[i]==a[i-1]+1:
    res+=1
  else:
    res+=a[i]
print(res)

Solution (Python):
N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

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

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

Solution (Python):
N=int(input())
A=[int(input()) for _ in range(N)]

ans=0
if A[0]!=0:
    print(-1)
    exit()
for i in range(N-1,0,-1):
    l,a=A[i-1],A[i]
    if a>l+1:
        print(-1)
        exit()
    elif a==l+1:
        ans+=1
    elif a!=0:
        ans+=a
print(ans)

Solution (Python):

N = int(input())
a=[]
for i in range(N):
    a.append(int(input()))

def main():
    flag = 0
    tmp = a[-1]
    ans = 0
    
    for aa in reversed(a[:-1]):
        if aa >= tmp:
            ans += tmp
            tmp = aa
        elif aa +1 == tmp:
            ans += 1
            tmp = aa
        else:
            return -1

    if a[0] != 0:
        ans = -1
    return ans
            
print(main())

Solution (Python):
n = int(input())
A = [int(input()) for i in range(n)]

ng = 0
if A[0] != 0:
    ng = 1
ans = 0
for i in range(1, n):
    if A[i] > A[i-1] and A[i] - A[i-1] > 1:
        ng = 1
        break
    elif A[i] <= A[i-1]:
        ans += A[i]
    else:
        ans += 1

if ng == 0:
    print(ans)
else:
    print(-1)

Solution (Python):
n=int(input())
c=[int(input())for i in range(n)]
d=0
p=0
for i in range(n-1,0,-1):
    if c[i]-c[i-1]>1:
        print(-1)
        break
    else:
        if d!=c[i]:
            p+=c[i]
            d=c[i]
    d-=1
else:
    print(-1if c[0]>0else p)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)

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

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