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




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

    count = 0

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

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

        X[i] = max(0, X[i + 1] - 1)
        if A[i] == X[i]:
            continue

        count += A[i]
        X[i] = A[i]

    print(count)


if __name__ == '__main__':
    main()

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

Ans = 0
if A[0]>0:
    print(-1)
else:
    for i in range(N-1):
        d = A[N-1-i]-A[N-2-i]
        if d>1:
            print(-1)
            sys.exit()
        elif d<=0:
            Ans += A[N-1-i]
        elif d==1:
            Ans += 1
    print(Ans)

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

def solve(a):
  if a[0]!=0:
    return -1
  ans=0
  for i in range(1,len(a)):
    if a[i]==a[i-1]+1:
      ans+=1
    elif a[i]<=a[i-1]:
      ans+=a[i]
    else:
      return -1
  return ans

print(solve(A))

Solution (Python):

from itertools import combinations
def inpl(): return map(int, input().split())

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

if P[0] != 0 or any([P[i+1] - P[i] > 1 for i in range(N-1)]):
    print(-1)
else:
    ans = 0
    r = N-1
    now = 0
    for r in range(N)[::-1]:
        if P[r] != now:
            ans += P[r]
            now = P[r]
        now -= 1
    print(ans)

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

A=[-1]*(N+1)

for i in range(1,N+1):
    A[i]=int(input())
A=A+[0]

count=0

for j in range(N,0,-1):
    if A[j]<=A[j-1]+1:
        if A[j]==A[j+1]-1:
            continue
        else:
            count+=A[j]
    else:
        count=-1
        break


print(count)

Solution (Python):
N = int(input())
A = []
flag = True
for i in range(N):
	a = int(input())
	if i == 0:
		if a > 0:
			flag = False
	if i > 0:
		if a > A[i-1] + 1:
			flag = False
	A.append(a)

if not flag:
	print(-1)
	exit()
A.reverse()
last = 0
ans = 0
for i in range(N):
	a = A[i]
	if a != last - 1:
		ans += a
	last = a
print(ans)

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

count=0
be=0
if a[0]==0:
    for i in a[1:]:
        
        if i<=be+1:
            if i>be: count+=1
            else: count +=i
            be=i
        else:
            print('-1')
            break
    else:print(count)
else: print('-1')

Solution (Python):


n=int(input())
A=[int(input()) for i in range(n)]
flag=1
ans=0
c=0
M=0
while(A):
    a=A.pop()
    M-=1
    n-=1
    if n < a:
        flag = 0

        break

    if M > a:
        flag = 0

        break
    M=max(M,a)

    
    if c == 0:
        ans+=a

    if n==0:
        break

    if a-1 == A[-1]:

        c=1
    else:

        c=0

        

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

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

cmax = -1
for i in range(N):
	if A[i] > cmax + 1:
		print(-1)
		sys.exit(0)
	elif A[i] == cmax + 1:
		cmax += 1
	else:
		cmax = A[i]
		
res = 0
for i in range(N-1):
	if A[i] + 1 != A[i+1]:
		res += A[i]

res += A[N-1]

print(res)

Solution (Python):
N = int(input())
n0 = -1
c = 0
T = False
for i in range(N):
    n = int(input())
    if n > n0+1:
        T = True
    elif n == n0+1 and i != 0:
        c += 1
    else:
        c += n
    n0 = n
if T:
    print(-1)
else:
    print(c)

Solution (Python):
N = int(input())
a = [0]*N
div = []
flg = 0
for i in range(N):
	a[i] = int(input())
	if i != 0:
		if (a[i] - a[i-1]) > 1:
			flg = 1
		if a[i-1] > a[i]:
			div.append(i)

div.append(N)

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

ans = 0
p = 0
for index in div:
	s = a[index-1]
	for i in range(index-1,p,-1):
		if a[i] == a[i-1]:
			s += a[i-1]
	ans += s
	p = index

print(ans)

Solution (Python):

N = int(input())

prev = 0
ans = 0
flag = True
for i in range(N):
	now = int(input())
	
	if now - prev > 1 or (i == 0 and now != 0):
		print(-1)
		flag = False
		break
	elif now - prev == 1:
		ans += 1
	elif now:
		ans += now
	prev = now
if flag:
	print(ans)

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

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

Solution (Python):

def solve():
    N = int(input())
    ans = 0
    prev = None
    for _ in range(N):
        a = int(input())    
        if prev is None and a!=0:
            return -1
        if prev is not None:
            diff = a - prev
            if diff >= 2:
                return -1
            elif diff <= 0:
                ans += prev
        prev = a
    ans += prev
    return ans

if __name__=='__main__':
    print(solve())

Solution (Python):


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

res = 0
for i in range(n):

    if a[i] > i:
        res = -1
        break
    
    if i > 0:
        if a[i] - a[i-1] > 1:
            res = -1
            break
        elif a[i] - a[i-1] != 1:
            res += a[i-1]

    if i == n - 1:
        res += a[i]

print(res)

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

ans = 0
for i in range(N)[::-1]:
  if A[i] > i or (i > 0 and 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):
n = int(input())
alst = [int(input()) for i in range(n)]

flag = 0
ans = 0
temp = -1
ind = 0
while ind < n:
  a = alst[ind]
  if a - temp > 1:
    flag = 1
    break
  while ind + 1 < n and alst[ind + 1] == a + 1:
    ind += 1
    a = alst[ind]
  ans += a
  temp = a
  ind += 1

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

Solution (Python):
N=int(raw_input())
ans=0
A=[]
for i in range(N):
    A.append(int(raw_input()))
Ar=list(reversed(A))
tmp=Ar[0]
for i in range(0, N-1):
    if (Ar[i] - Ar[i+1]) > 1:
        ans = -1
        break
    elif (Ar[i] - Ar[i+1]) != 1:
        if i+Ar[i] >= N:
            ans = -1
            break
        ans += tmp
        tmp =Ar[i+1]
if Ar[N-1]!=0:
    ans = -1
if ans != -1 and Ar[N-1]==0 and Ar[N-2]==1:
    ans+=tmp

print ans

Solution (Python):

import numpy as np

n = int(raw_input())
a = np.zeros([n],int)
for i in range(n):
    a[i] = int(raw_input())

count = 0

i = n-1
if not a[0] == 0:
    count = -1
else:
    while i > 0:
        if a[i-1] >= a[i]:
            count += a[i]
        elif a[i-1] == a[i]-1:
            count += 1
        else:
            count = -1
            break
        i -= 1

print count

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

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

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

print(c)

Solution (Python):
from copy import deepcopy
import itertools


def read():
    return int(input())


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


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


N = read()
A = []
for _ in range(N):
    A.append(read())

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

print(ans)

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = map(int, stdin.read().split(), repeat(10, n))
    s = p = 0
    for x in reversed(a):
        p -= 1
        if p < 0:
            p = 0
        if x < p:
            print -1
            return
        if x > p:
            s += x
            p = x
    if p:
        print -1
        return
    print s
main()

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

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

Solution (Python):
n=input()
last=-1

now=0
ans=-1
for i in range(n):
    now=input()
    if now>i or now-last>1:
        print -1
        break
    if now==last+1:
        ans+=1
    elif now<=last:
        ans+=now
    last=now
else:
    print ans

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

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    n = f.read_int()
    a = [0] * n
    for i in xrange(n):
        a[i] = f.read_int()

    if a[0] != 0: return -1
    cur = 0
    ans = 0

    for i in xrange(1,n):
        if a[i] - cur > 1:
            return -1
        elif a[i] - cur == 1:
            ans += 1
        else:
            ans += a[i]
        cur = a[i]

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
if a[0]:
    print(-1)
else:
    s = 0
    for i in range(1, n):
        if a[i] == a[i - 1] + 1:
            s += 1
        elif a[i] > a[i - 1] + 1:
            s = -1
            break
        else:
            s += a[i]
    print(s)

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

Solution (Python):



def sub(n, values):
	cnt = 0
	tmp = -1

	for val in values:
		
		if val == tmp + 1:
			tmp = val
		elif val <= tmp:
			cnt += tmp
			tmp = val
		else:
			cnt = -1
			return(cnt)
	
	cnt += tmp
	return(cnt)

def main():
	n = int(input())
	values = [int(input()) for _ in range(n)]
	print(sub(n, values))

if __name__ == '__main__':
	main()

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

Solution (Python):
exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

import itertools

A = nAuto(nAuto())
n = 0
ba = 0
for a in reversed(A):
    if ba<=a:
        n += a
    elif a+1==ba:
        pass
    else:
        print(-1)
        exit()
    ba = a

if ba!=0:
    print(-1)
    exit()

print(n)

Solution (Python):

N = int(input())

res = 0
A_list = []
for i in range(N):
    A_list.append(int(input()))
for i in range(N):
    if i == 0:
        if A_list[i] != 0:
            res = -1
            break
    else:
        if A_list[i] > A_list[i-1] + 1:
            res = -1
            break
        elif A_list[i] == A_list[i-1] + 1:
            res += 1
        else:
            res += A_list[i]
print(res)

Solution (Python):
N = int(input())
ans = -1
bef = -1
for i in range(N):
    now = int(input())
    if now - bef > 1:
        ans = -1
        break
    elif now - bef == 1:
        ans += 1
        bef = now
    else:
        ans += now
        bef = now
 
print(str(ans))

Solution (Python):


import sys

input=sys.stdin.readline

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

bad=(a[0]!=0)
for i in range(n-1):
    if a[i]+1<a[i+1]:
        bad=True

if bad: print(-1)
else:
    
    ans=[0]*n
    for i in range(n):
        ans[i-a[i]]=a[i]
    print(sum(ans))