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 = sys.stdin.readline
N = int(input())

pre = int(input())
if pre != 0:
    print(-1)
    sys.exit()
ans = 0
for _ in range(N-1):
    x = int(input())
    if pre + 1 < x:
        print(-1)
        sys.exit()
    elif pre + 1 == x:
        ans += 1
    else:
        ans += x
    pre = x

print(ans)

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

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()

n=ip()
ans=[]
a=[-1]
out=0
now_max=0

for i in range(n):
  s=ip()
  if a[-1]+2<=s:
    out+=1
    break
  elif a[-1]>s:
    ans.append(now_max)
    now_max=s
    if i==n-1:
      ans.append(now_max)
  elif a[-1]==s:
    ans.append(now_max)
    if i==n-1:
      ans.append(now_max)
  elif a[-1]+1==s:
    now_max=s
    if i==n-1:
      ans.append(now_max)
  a.append(s)
      
if out==0:
  print(sum(ans))
else:
  print(-1)

Solution (Python):
def main():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))
    x = a[-1]
    ans = a[-1]
    for i in range(1,n):
        if x==0:
            x = a[-1-i]
        e = x-1
        if e>a[-1-i]:
            print(-1)
            return
        elif e<a[-1-i]:
            x = a[-1-i]
            ans += a[-1-i]
        else:
            x -= 1
    if x==0:
        print(ans)
    else:
        print(-1) 

if __name__ == "__main__":
    main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




def main():
	n=II()
	A=[II() for _ in range(n)]+[0]


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

	ans=0

	for i,j in zip(A[:-1],A[1:]):
		if j-i>=2:
			print(-1)
			exit()
		elif j-i<=0:
			ans+=i

	print(ans)












if __name__ == "__main__":
	main()

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

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

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

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


N, *A = map(int, open(0).read().split())
if A[0] != 0:
    terminate()

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inp() for _ in range(n)]
res = 0
for i in range(1,n)[::-1]:
    if a[i]-a[i-1] == 1:
        res += 1
    else:
        res += a[i]
for i in range(n-1):
    if a[i+1] - a[i] > 1:
        res = -1
if a[0] != 0:
    res = -1 
print(res)

Solution (Python):
n, *a = map(int, open(0).read().split())









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


i = n - 1
ans = 0
while i > 0:
	ans += a[i]
	while i > 0 and a[i] - 1 == a[i - 1]:
		i -= 1
	i -= 1
print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
flag = 0
cnt = A[N-1]
for i in range(N-2,-1,-1):
    if A[i]==A[i+1]-1:continue
    elif A[i]>=A[i+1]:
        if A[i]>0:
            cnt += A[i]
    else:
        flag = 1
        break
if A[0]>0 or flag==1:
    print(-1)
else:
    print(cnt)

Solution (Python):
n, *a = map(int, open(0).read().split())


ok = True
for i in range(n - 1):
    if a[i + 1] - a[i] > 1:
        ok = False
if not ok or a[0] != 0:
    print(-1)
    exit()


ans = 0
a = list(reversed(a))
i = 0
while i < n:
    ans += a[i]
    while i < n - 1 and a[i] - 1 == a[i + 1]:
        i += 1
    i += 1
print(ans)

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

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

f=True
t=0
c=0
for i in a:
  if i==t:
    t-=1
  elif i<t:
    f=False
    break
  else:
    t=i-1
    c+=i
if t!=-1:
  f=False
print(c if f else -1)

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

def main(N, A):
    if A[0] != 0: return -1
    if any([A[i+1] - A[i] > 1 for i in range(N-1)]): return -1
    A.reverse()
    ans = 0
    before = -1
    for a in A:
        if a+1 != before:
            ans += a
        before = a
    return ans

print(main(N, A))

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

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

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

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

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

cnt=0
for i in range(1,n):
    if A[i-1]+1==A[i]:
        cnt +=1
    elif A[i-1]==A[i] or A[i-1]>A[i]:
        cnt +=A[i]
    else:print(-1);exit()

print(cnt)

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

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

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

print(cnt)

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

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

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

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

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

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

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

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

Solution (Python):
n = int(input())
a = [int(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 = a[i] - 1
else:
    print(ans if a[0] == 0 else - 1)

Solution (Python):
n = int(input())
a = [0]*n
a = [int(input()) for i in range(n)]
if a[0] != 0:
    ans = -1
    

else:
    b = a[::-1]
    ans = 0
    for i in range(n-1):
        if abs(b[i] - b[i+1]) <= 1:
            if b[i] > b[i+1]:
                ans += 1
            else:
                ans += b[i]
            
        else:
            if b[i] < b[i+1]:
                ans += b[i]
            else:
                ans = -1
                break
print(ans)

Solution (Python):
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
A.append(0)
if A[0]!=0:
    print(-1)
    exit()
a0 = 0
res = 0
for a in A:
    if a0 >= a:
        res += a0
    elif a - a0 >= 2:
        print(-1)
        exit()
    a0 = a
print(res)

Solution (Python):

N = int(input())

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

res = 0
last = N
for i,a in zip(reversed(range(N)), reversed(A)):
    j = i-a
    if j > last or j < 0:
        res = -1
        break
    elif j < last:
        last = j
        res += a

print(res)

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

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

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

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

Solution (Python):
def solve(a):
    if a[0][0] != 0:
        return -1
    res = 0
    for aa in a:
        for i in range(len(aa)):
            if i == 0:
                res += aa[i]
            elif aa[i - 1] + 1 == aa[i]:
                res += 1
            elif aa[i - 1] == aa[i]:
                res += aa[i]
            else:
                return -1
    return res


def main():
    n = int(input())
    a = [[]]
    last_a = 0
    for _ in range(n):
        now = int(input())
        if last_a > now:
            a.append([])
        a[-1].append(now)
        last_a = now
    print(solve(a))


if __name__ == '__main__':
    main()

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

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = [I() for _ in range(N)]

    is_ok = True

    
    if [A[i] for i in range(N) if A[i] > i]:
        is_ok = False
    else:
        for i in range(N - 1):
            if A[i] + 1 < A[i+1]:
                is_ok = False
                break

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

    if is_ok:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    n=I()
    lis=LI2()
    ind=[i for i in range(n)]
    if lis[0]!=0:
        print(-1)
        sys.exit()
    for i in range(1,n):
        if lis[i]==0:
            ind[i]=0
        else:
            ind[i]=ind[i-1]+1
    for i in range(n):
        if lis[i]>ind[i]:
            print(-1)
            sys.exit()
    ans=0
    for i in range(n-1):
        x=lis[i]
        if lis[i+1]==lis[i]+1:
            continue
        elif lis[i+1]>lis[i]+1:
            print(-1)
            sys.exit()
        else:
            ans+=x
    if n!=1 and lis[-1]==lis[-2]+1:
        ans+=lis[-1]
    else:
        ans+=lis[-1]
    
    print(ans)
            
            
            
            
        
    
    
    
    



if __name__=="__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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

    ans = 0
    prev_a = -1
    for i, a in enumerate(A):
        if (a > i) or (a > prev_a + 1):
            ans = -1
            break

        if a > 0:
            ans += 1
            if prev_a + 1 != a:
                ans += (a - 1)

        prev_a = a

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    a_ = int(input())
    if a_ != 0:
        print(-1)
        return True
    for n in range(N-1):
        a = int(input())
        if a - a_ > 1:
            print(-1)
            return True
        if a - a_ == 1:
            ans += 1
            a_ = a
        else:
            ans += a
            a_ = a
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
ans = -1
prev = -1
for _ in range(n):
    a = int(input())
    if prev+1 == a:
        prev = a
        ans += 1
        continue
    if prev+1 < a:
        print(-1)
        break
    ans += a
    prev = a
else:
    print(ans)

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

ans = A[-1]
for a, prev_a in reversed(tuple(zip(A, A[1:]))):
    if a == prev_a-1:
        continue
    if a < prev_a-1:
        print(-1)
        break
    ans += a
else:
    print(ans)

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
cnt = 0

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

else:
    before = a1
    for i in range(1,N):
        a1 = int(input())
        if a1 == 0:
            continue
        elif a1==before+1:
            cnt += 1
        elif a1 <= before:
            cnt += a1
        else:
            print(-1)
            exit()
        before = a1
    print(cnt)

Solution (Python):
import sys
import math
import collections
import bisect
import copy
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n = ni()
    a = [ni() for _ in range(n)]
    ans = 0

    prev = -1
    for i, ai in enumerate(reversed(a)):
        if ai > n - i - 1:
            print(-1)
            exit(0)

        if i == 0:
            ans += ai
        else:
            if ai != prev - 1:
                if ai > prev - 1:
                    ans += ai
                else:
                    print(-1)
                    exit(0)
        prev = ai
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import copy
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n = ni()
    a = [ni() for _ in range(n)]
    ans = 0

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

    prev = -1
    for i, ai in enumerate(reversed(a)):
        if ai > n - i - 1:
            print(-1)
            exit(0)

        if i == 0:
            ans += ai
        else:
            if ai != prev - 1:
                if ai > prev - 1:
                    ans += ai
                else:
                    print(-1)
                    exit(0)
        prev = ai
    print(ans)

if __name__ == '__main__':
    main()

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

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


cnt=0

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

for ii in range(1,n):
    i=n-ii
    if a[i]==0:
        continue
    elif a[i]<=a[i-1]:
        cnt+=a[i]
    elif a[i]==a[i-1]+1:
        cnt+=1
    elif a[i]>a[i-1]+1 or  a[i]>i:
        print(-1)
        exit()
    
    

print(cnt)

    
"""
t: 0 1 1 0 1 2 2 1 2
s: 0 0 0 0 0 0 0 0 0
1: 0 0 1 0 0 0 0 0 0
2: 0 1 1 0 0 0 0 0 0
3: 0 1 1 0 0 0 0 1 0
4: 0 1 1 0 0 0 0 1 2
5: 0 1 1 0 0 1 0 1 2

"""

Solution (Python):
n = int(input())
alst = [int(input()) for _ in range(n)]
ans = 0
bef = 0
if alst[0] != 0:
    print(-1)
    exit()
    
for num in alst[1:]:
    if num == bef + 1:
        pass
    elif num > bef + 1:
        print(-1)
        exit()
    else:
        ans += bef
    bef = num
ans += bef
print(ans)

Solution (Python):
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(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(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 

from decimal import *



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] or A[i] < tmp:
		print(-1)
		exit()
	elif tmp < A[i]:
		cnt += A[i]
		tmp = A[i]

print(cnt)

Solution (Python):
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(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(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 

from decimal import *



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)

Solution (Python):
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(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(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 

from decimal import *



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)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    A = []
    for _ in range(n):
        A.append(int(input()))
    mae = -1
    ans = -1
    for AA in A:
        if AA > mae+1:
            print(-1)
            break
        elif AA == mae+1:
            ans += 1
        else:
            ans += AA
        mae = AA
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[I() for _ in range(n)]

  if l[0]!=0:
    return -1

  ans=0
  st=l[0]
  for x in l[1:]:
    if st+1<x:
      return -1

    if x==st:
      ans+=x

    elif st<x:
      ans+=1

    elif st>x:
      ans+=x

    st=x

  return ans


print(main())

Solution (Python):
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    if A[0] > 0:
        print(-1)
        return
    for n in range(N - 1):
        if  A[n + 1] >= A[n] + 2:
            print(-1)
            return
    
    A = A[::-1]
    ans = A[0]
    for n in range(N - 1):
        if A[n + 1] >= A[n]:
            ans += A[n + 1]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

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

    ans = 0
    for a, b in zip(A[0:], A[1:]):
        if b - a >= 2:
            print(-1)
            return
        elif b - a == 1 or (a == 1 and a == b):
            ans += 1
        else:
            ans += b

    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):



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

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

    
    
    
    
    
    
    

    
    
    for pre, cur in zip(a, a[1:]):
        if pre + 1 < cur:
            print(-1)
            exit()

        if pre + 1 == cur:
            ans += 1
        else:
            ans += cur

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

class TwoDimGrid:
    
    def __init__(self, h, w, wall="
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])

    def search(self, s, g):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]



def solve():
    n = getN()
    nums = []
    for i in range(n):
        nums.append(getN())
    
    
    
    
    
    
    
    
    
    
    
    
    
    if nums[0] != 0:
        print(-1)
        return
    prev = 0
    ans = 0
    for num in nums[1:]:
        if num > prev + 1:
            print(-1)
            return
        if num == prev + 1:
            ans += 1
        if num<= prev:
            ans += num
        prev = num
    print(ans)
    return
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    if A[0] > 0:
        print(-1)
        return
    ans = 0
    for i in range(1,N):
        
        if A[i] == 0:
            continue
        if A[i] == 1:
            ans += 1
            continue
        if A[i] == A[i-1]+1:
            ans += 1
            continue
        if A[i] <= A[i-1]:
            ans += A[i]
            continue
        print(-1)
        return
    print(ans)
if __name__ == '__main__':
    main()

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 a+1 < b:
        print(-1)
        exit()
    if a+1 == b:
        ans += 1
    else:
        ans += b
print(ans)

Solution (Python):
def solve():
  N = int(input())
  A = [int(input()) for _ in range(N)]
  if N==1:
    if A[0]==0:
      return 0
    return -1
  if A[0]>0 or A[1]>1:
    return -1
  ans = N - A.count(0)
  for i in range(1,N-1):
    if A[i]+1<A[i+1]:
      return -1
    if A[i]>=A[i+1] and A[i+1]>0:
      ans += A[i+1]-1
  return ans
print(solve())

Solution (Python):
n=int(input())
if int(input())!=0:
  print(-1)
  exit()
b=0
c=0

for i in range(n-1):
  a=int(input())
  if a>b+1:
    print(-1)
    exit()
  else:
    if a==b+1:
      c+=1
    else:
      c+=a  
  b=a
print(c)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    ans = -1
    prev = -1

    for x in a:
        if prev >= x:
            ans += x
            prev = x
        elif prev + 1 == x:
            ans += 1
            prev = x
        else:
            return print(-1)

    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
n = int(input())
As = [int(input()) for i in range(n)]
dp  = [0] * n 
mx = 0
prev = 0
for i,a in enumerate(As):
    if a == 0:continue
    
    if prev + 1 < a:
        print(-1)
        exit()
    if i - a < mx: 
        print(-1)
        exit()
    else:
        dp[i-a] = a
        mx = i-a
    prev = a
print(sum(dp))

Solution (Python):
import sys
N = int(input())
pre_a = int(input())
if pre_a != 0:
    print(-1)
    sys.exit()
ans = 0
for i in range(N-1):
    ai = int(input())
    if ai - pre_a < 1:
        ans += ai
    elif ai - pre_a == 1:
        ans += 1
    else:
        ans = -1
        break
    pre_a = ai

print(ans)