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):
N = int(input())
cnt = 0
A = [int(input()) for _ in range(N)]
if A[0]!=0:
    cnt = -1
else:
    for i in range(1,N):
        if A[i]==A[i-1]+1:
            continue
        elif A[i]<=A[i-1]:
            cnt += A[i-1]
        else:
            cnt = -1
            break
    if cnt>=0:
        cnt += A[N-1]
print(cnt)

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

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

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

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

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.append(A[-1])
    
    if A[0] != 0:
        print(-1)
        exit()
    else:
        ans = 0
        now = 0
        for i in range(N):
            i += 1
            if A[i] == now + 1:
                now = A[i]
            elif A[i] == now:
                ans += now
            elif now > A[i]:
                ans += now
                now = A[i]
            else:
                print(-1)
                exit()
                
    print(ans)
    
if __name__ == "__main__":
    main()

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

ans = 0

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

print(ans)

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

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

A = [0] + A[::-1]
answer = 0
for i in range(1, len(A)):
  if A[i] and A[i] - A[i - 1] >= 0:
    answer += A[i]
print(answer)

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

ans = -1
tmp = -1 
for i in range(N):
    A = int(input())
    if A > i:
        print (-1)
        exit()
    if tmp + 1 < A:
        print (-1)
        exit()
    if tmp + 1 == A:
        ans += 1
        tmp += 1
    else:
        ans += A
        tmp = A

print (ans)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
B = []
if A[0] != 0:
  p = -1
else:
  p = 0
for i in range(1, N):
  if A[i] - A[i-1] >= 2:
    p = -1
  elif A[i] - A[i-1] <= 0:
    B.append(i-1)
if p == -1:
  print(p)
else:
  print(sum(A[B[i]] for i in range(len(B))) + A[N-1])

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

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 0
for i, a in enumerate(A):
    if a > i:
        break
    if i == 0:
        continue
    if a == A[i-1]+1:
        ans += 1
    elif a <= A[i-1]:
        ans += a
    else:
        break
else:
    print(ans)
    exit()
print(-1)

Solution (Python):
def main(n, A):
    if A[0] != 0:
        return -1

    A.append(0)
    A = A[::-1]

    res = 0
    for x, y in zip(A[:-1], A[1:]):
        if x <= y:
            res += y
        elif x - 1 == y:
            pass
        else:
            return -1

    return res


if __name__ == "__main__":
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = main(n, a)
    print(ans)

Solution (Python):
import sys

n = int(sys.stdin.readline().strip())
a_ls = []
for i in range(n):
    a = int(sys.stdin.readline().strip())
    a_ls.append(a)

if a_ls[0] != 0:
    print(-1)
else:
    cur = a_ls[-1]
    res = cur
    for a in a_ls[::-1][1:]:
        cur -= 1
        if a - cur > 0:
            res += a
            cur = a
        elif a == cur:
            continue
        else:
            res = -1
            break
    print(res)

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


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

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


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

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

flag = (A[0] == 0)
ans = 0

for i in range(1, N):
    d = A[i] - A[i - 1]
    if d > 1:
        flag = False
    elif d == 1:
        ans += 1
    else:
        ans += A[i]

if flag is False:
    ans = -1

print(ans)

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

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

  for i in range(1, N) :
    if A[i] - A[i-1] >= 2:
      return -1

  ret = 0
  for i in range(1, N) :
    if A[i] == 0 :
      continue

    ret += 1
    if A[i] != A[i-1] + 1 :
      ret += A[i] - 1
  
  return ret

print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N): a.append(int(input()))
if a[0] != 0:
  print(-1)
  exit(0)
for i in range(N - 1):
  if a[i + 1] > a[i] and (a[i + 1] - a[i] > 1):
    print(-1)
    exit(0)
res = 0
s = 0
x = 1
for i in range(1, N):
  if a[i] == x:
    s += 1
  else:
    if x > 0: res += (s - 1) * x + 1
    if x > a[i] and a[i] > 1:
      res += a[i] - 1
    s = 1
    x = a[i]
  
if x > 0: res += (s - 1) * x + 1
print(res)

Solution (Python):

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

ans = 0
tmp = 0
flag = True
if a[0] != 0:
    flag = False

for i in range(n-1):
    if a[i+1] > a[i]:
        pass
    else:
        ans += a[i]
    if a[i+1] - a[i] > 1:
        flag = False
    
ans += a[n-1]

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

Solution (Python):
n, *a = map(int, open(0).read().split())
ans = 0
if a[0] != 0:
	print(-1)
	exit()
for x, y in zip(a, a[1:]+[0]):
	if x + 1 < y:
		print(-1)
		exit()
	if x >= y:
		ans += x
print(ans)

Solution (Python):
def examC():
    N = I(); A = [I() for _ in range(N)]
    cur = -1; ans = -1
    for i in range(N):
        if A[i]>cur+1:
            ans = -1
            break
        elif A[i]==cur+1:
            cur +=1
            ans +=1
        else:
            ans += A[i]
            cur = A[i]
    print(ans)


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())
A = [int(sys.stdin.buffer.readline()) for _ in range(N)]


if A[0] > 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
    elif b > 0:
        ans += b
print(ans)

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

N, *A = map(int, read().split())

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


answer = 0
A.append(0)
for i in range(N):
    if A[i + 1] - A[i] > 1:
        print(-1)
        exit()
    if A[i + 1] <= A[i]:
        answer += A[i]

print(answer)

Solution (Python):
import sys
n=int(input())
a=[int(input()) for i in range(n)]
for i in range(n):
  if a[i]>i:
    print(-1)
    sys.exit()
ct=0
for i in range(n-1,0,-1):
  if a[i]-1>a[i-1]:
    print(-1)
    sys.exit()
  elif a[i]-1==a[i-1]:
    ct+=1
  else:
    ct+=a[i]
print(ct)

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

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

ans=0
for i in reversed(range(1,N)):
  if A[i]==A[i-1]+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 or any(a[i+1]-a[i]>1 for i in range(n-1)):
    print(-1)
    exit(0)
ans = 0
for i in range(1,n):
    if a[i] == a[i-1] + 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 = []
l = 0
for i in range(1, N):
  if A[i] > A[i - 1] + 1:
    print(-1)
    exit()
    
  if A[i] == A[i - 1] + 1:
    l = A[i]
  else:
    ans.append(l)
    l = A[i]
ans.append(l)
print(sum(ans))

Solution (Python):
import sys
input = sys.stdin.readline
cur = -1
c = 0
for i in range(int(input())):
  pre,cur = cur,int(input())
  if cur == 0:
    continue
  elif cur == pre + 1:
    c += 1
  elif cur <= pre:
    c += cur
  else:
    print(-1)
    exit()
print(c)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
cur = -1
c = 0
for i in a:
  pre,cur = cur,i
  if cur == 0:
    continue
  elif cur == pre + 1:
    c += 1
  elif cur <= pre:
    c += cur
  else:
    print(-1)
    exit()
print(c)

Solution (Python):


import sys
input = sys.stdin.readline

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

judge = 1
for i in range(N):
    if i != N-1:
        if A[i+1] <= A[i]+1 and A[i] <= i:
            pass
        else:
            judge = 0
    else:
        if A[i] <= i:
            pass
        else:
            judge = 0

if judge == 0:
    print(-1)
else:
    n = 1
    if A[N-1] == 0:
        n = 0
    for i in range(N-1):
        if A[(N-2)-i] == 0:
            n = n
        elif A[(N-2)-i] < A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + 1
        elif A[(N-2)-i] == A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + A[(N-2)-i]
        elif A[(N-2)-i] > A[(N-1)-i] and A[(N-1)-i] != 0:
            n = n + A[(N-1)-i]
        else:
            n = n + 1
    print(int(n))

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g

def main():
    n=inp()
    a=inplm(n)
    ans=0
    if a[0]!=0:
        print(-1)
        return
    for i in range(n-1):
        if a[i+1]>a[i]+1:
            print(-1)
            return
        if a[i+1]==a[i]:
            ans+=a[i]
        elif a[i+1]>a[i]:
            ans+=1
        elif a[i]>a[i+1]:
            ans+=a[i+1]
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
A = [0] * N
for i in range(N):
    A[i] = int(stdin.readline().rstrip())

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

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

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

Solution (Python):
import sys
input=sys.stdin.readline
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]>a[i-1]+1:
        print(-1)
        exit()
    if a[i]<=a[i-1]:
        ans+=a[i-1]
ans+=a[n-1]

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
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]>a[i-1]+1:
        print(-1)
        exit()
    if a[i]==a[i-1]+1:
        ans+=1
    else:
        ans+=a[i]

print(ans)

Solution (Python):
import numpy as np

N = int(input())
A = np.array([int(input()) for _ in range(N)] + [0], dtype='int64')

x = (A[:-1][A[:-1] >= A[1:]]).sum()

if A[0] != 0:
    x = -1
if (A[1:] >= A[:-1] + 2).any():
    x = -1

print(x)

Solution (Python):

from collections import defaultdict


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


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

	if A[0] != 0:
		print(-1)
	else:
		judge = "Yes"
		ans = 0
		for i in range(N - 1):
			if A[-1 - i] == A[-2 - i] + 1:
				ans += 1
			elif A[-1 - i] <= A[-2 - i]:
				if A[-1 - i] <= N - 1 - i:
					ans += A[-1 - i]
				else:
					judge = "No"
					break
			else:
				judge = "No"
				break
		if judge == "No":
			print(-1)
		else:
			print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
def solve(n, a):
    if a[0] != 0:
        return -1

    if any(x > 1 for x in (t - s for s, t in zip(a, a[1:]))):
        return -1

    p = None
    ans = 0
    for c in reversed(a):
        if p is None or c != (p - 1):
            ans += c
        p = c
    return ans


if __name__ == '__main__':
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(solve(n, a))

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]-a[i-1]>1:
        print(-1)
        exit()
    elif a[i]<=a[i-1]:
        ans+=a[i]
    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()

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

Solution (Python):
import sys

N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

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

A.reverse()

ans = 0

for i in range(N):

    if i == 0:
        ans += A[i]

    else:

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

        elif A[i-1] -1 == A[i]:
            pass

        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
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)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

    subA = []
    prev = -1
    l = 0
    tmp_array = []
    while l < N:
        if A[l] > prev:
            tmp_array.append(A[l])
            prev = A[l]
        else:
            prev = A[l]
            subA.append(tmp_array)
            tmp_array = [prev]

        l += 1
    subA.append(tmp_array)
    ans = sum([max(l) for l in subA])
print(ans)

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

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

def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    if A[0] != 0:
        print(-1)
        return
    dp = [0] * N
    for i in range(1, N):
        if A[i] > A[i-1] + 1:
            print(-1)
            return
        elif A[i] == A[i-1] + 1:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1] + A[i]
    
    print(dp[-1])

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
if A[0]:
    print(-1)
    exit()
ans = 0
dp = A[-1]
for a, b in zip(A[-2::-1], A[-1::-1]):
    if a == b - 1:
        continue
    elif a >= b:
        ans += dp
        dp = a
    else:
        print(-1)
        exit()
print(ans + dp)

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

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

n = int(input())
pre = -1
ans = -1
for i in range(n):
    a = int(input())
    if a > i or a > pre + 1:
        print(-1)
        exit()

    if a <= pre:
        ans += a
    else:
        ans += 1
    pre = a

print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
a += [a[-1]]
def end():
    print(-1)
    exit()

if a[0] != 0:
    end()

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

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

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


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

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

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

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

print(ans)

Solution (Python):

def main():
    N, *A = map(int, open(0))
    if A[0]:  
        print(-1)
        return
    A.append(0)
    ans, B = 0, A[::-1]
    for i, j in zip(B, B[1:]):  
        if i > j + 1:  
            print(-1)
            return
        if j >= i:  
            ans += j
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    N, *A = map(int, open(0))
    A.append(0)
    if A[0]:  
        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()

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

ans = 0
p = 0
for i in range(1,N+1):
  if ls[i-1]+1<ls[i]:
    print(-1)
    break
  if ls[i-1]+1==ls[i]:
    if i==N:
      ans += (ls[i])
    p = ls[i]
    continue
  else:
    if i==N:
      ans += ls[i]
    ans += p
    p = ls[i]
else:
  print(ans)

Solution (Python):
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
ans=0
chk=True
cur=0
for i in reversed(range(n)):
  if A[i]==cur:
    cur-=1
    continue
  else:
    if A[i]>i or A[i]<cur:
      chk=False
    else:
      ans+=A[i]
      cur=A[i]-1
print(ans if chk else -1)

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
def Solve(n,A):
    if n==1:
        return -1 if A[0]!=0 else 0
    else:
        ret=0
        for i in range(n):
            if i==0:
                if A[i]!=0:
                    return -1
            else:
                if A[i]==A[i-1]+1:
                    ret+=1
                elif A[i]<=A[i-1]:
                    ret+=A[i]
                else:
                    return -1
        return ret
print(Solve(N,A))

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


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

if t != 0:
    ans = -1
print(ans)

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

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

Solution (Python):
N=int(input())
A=[int(input()) for _ in range(N)]
tab = [0]*N
prev=10**10
for i,a in enumerate(A):
    dst = i-a
    if dst < 0 or dst >=N or (a>prev and a-prev>1):
        print(-1)
        exit()
    tab[dst] = max(tab[dst], a)
    prev = a
print(sum(tab))

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

ok = True
pre = -1
for i, a in enumerate(A):
    if a > pre + 1:
        ok = False
        break
    pre = a

if not ok:
    print(-1)
else:
    c = 0
    for i in range(N-1):
        if A[i+1] != A[i] + 1:
            c += A[i+1]
        else:
            c += 1
    print(c)

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

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

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

Solution (Python):


def solve(N, A):
    c = 0
    z = 0
    if A[0] != 0:
        return -1
    for i in range(1, N):
        if A[i] == 0:
            z = 0
            c+=A[i-1]
        elif A[i-1] < A[i] - 1:
            return -1
        elif A[i] <= i - z:
            if A[i] != A[i-1]+1:
                c += A[i-1]
        else:
            return -1
        
    c += A[-1]
    return c

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = [0]*N
    for i in range(N):
        A[i] = int(input())
    print(solve(N, A))

main()

Solution (Python):



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)

Solution (Python):



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)

Solution (Python):

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

Solution (Python):
import sys
n=int(input())
l=[0]*(n+1)
for i in range(n):
    l[i]=int(input())
    if l[i]>i:print(-1);sys.exit()
for i in range(n):
    if l[i]-l[i-1]>=2:print(-1);sys.exit()
ans=0
for i in range(n+1):
    if l[i]<=l[i-1]:
        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()

ans = 0
prev = 0

for a in reversed(A):
    if prev > 0:
        if a == (prev - 1):
            prev = a
            continue
        elif a < prev:
            print(-1)
            exit()
    ans += a
    prev = a

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(1, N):
    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())
a = [int(input()) for _ in range(n)]
if a[0] != 0:
  print(-1)
  exit(0)
cnt = 0
cur = 0
for i in range(n-1,-1,-1):
  if cur > a[i]:
    print(-1)
    exit(0)
  if cur < a[i]:
    cur = a[i]
    cnt += a[i]
  if cur > 0:
    cur -= 1
print(cnt)

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

import numpy as np

N = int(input())
A = np.array([int(input()) for x in range(N)] + [0], dtype=np.int64)

x = (A[:-1][A[:-1] >= A[1:]]).sum()

if (A > np.arange(len(A))).any():
    x = -1
if (A[1:] >= A[:-1] + 2).any():
    x = -1

print(x)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
A=[int(input()) for _ 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()
ans=0
prev=A[0]
for i,a in enumerate(A,1):
    if a==prev+1:
        ans+=1
    else:
        ans+=a
    prev=a
print(ans)

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

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

Solution (Python):
n=int(input())
arr=[int(input()) for _ in range(n)]
l=0
flag=True
for i in range(n):
  if arr[i]==0:
    l=1
  else:
    if arr[i]>l:
      flag=False
      break
    l+=1
  if i!=0:
    if arr[i]-arr[i-1]>=2:
      flag=False
      break
if flag==False:
  print(-1)
else:
  ans=arr[-1]
  tmp=arr[-1]
  for i in range(n-2,-1,-1):
    if arr[i]<tmp:
      tmp=arr[i]
    else:
      ans+=arr[i]
      if tmp!=arr[i]:
        tmp=arr[i]
  print(ans)

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

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