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



Sample input:
4
0
1
1
2


Sample output:
3

Submission status: Accepted

Solution code:
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] < A[i + 1] and A[i + 1] - A[i] != 1:
        print(-1)
        exit()
    if A[i] > i + 1:
        print(-1)
        exit()

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

Submission status: Accepted

Solution code:
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] < A[i + 1] and A[i + 1] - A[i] != 1:
        print(-1)
        exit()
    if A[i] > i + 1:
        print(-1)
        exit()

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

print(ans + A[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

def main():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))
    a.append(0)
    ans = solve(a, n)
    print(ans)

def solve(a, n):
    if not check(a, n):
        return -1

    base = 0
    s = 0
    for i in range(n):
        if a[i] > base + i:
            return -1
        
        if a[i + 1] <= a[i]:
            s += a[i]
        
        base = i - a[i]
    
    return s

def check(a, n):
    if a[0] != 0:
        return False
    
    for i in range(1, n):
        if a[i] - a[i - 1] > 1:
            return False

    return True

main()

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(input()) for _ 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()
    if nums[i] == 0:
        continue
    if nums[i] - nums[i-1] == 1:
        ans += 1
    else:
        ans += nums[i]
print(ans)

Submission status: Accepted

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

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

print(count)

Submission status: Accepted

Solution code:
n=int(input())
r=0
b=0
for i in range(n):
 t=int(input())
 if i==0!=t or b+1<t:print(-1);exit()
 elif b>=t:r+=b
 b=t
print(r+b)

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

Solution code:
k = 0
m = 0
d = int(input())
p = [0]*d
for i in range(d):
  p[i] = int(input())
  if i == 0:
    if p[0] != 0:
      print(-1)
      m = 1
      break
  else:
    if p[i]  <= p[i-1]:
      k += p[i]
    elif p[i] <= 1 + p[i-1]:
      k += 1
    else:
      print(-1)
      m = 1
      break
 
if m != 1:
  print(k)

Submission status: Accepted

Solution code:
k = 0
m = 0
d = int(input())
p = [0]*d
for i in range(d):
  p[i] = int(input())
  if i == 0:
    if p[0] != 0:
      print(-1)
      m = 1
      break
  else:
    if p[i]  <= p[i-1]:
      k += p[i]
    elif p[i] <= 1 + p[i-1]:
      k += 1
    else:
      print(-1)
      m = 1
      break

if m != 1:
  print(k)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
if A[0] != 0:
    print(-1)
else:
    count = 0
    prev = 0
    for i in range(1, N):
        temp = A[i] - prev
        if 0 < temp:
            if 2 <= temp:
                print(-1)
                break
            if A[i] == prev + 1:
                count += 1
            else:
                count += A[i]
            prev = A[i]
        else:
            count += A[i]
            prev = A[i]
    else:
        print(count)

Submission status: Accepted

Solution code:
import sys

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

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

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

A.append(0)

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

print(count)

Submission status: Accepted

Solution code:
import sys,collections,random,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
t = I()
if t != 0:
    print(-1)
    exit()
sums = 0
for i in range(n-1):
    c = I()
    if c-t > 1 or c > i+1:
        print(-1)
        exit()
    if c-t != 1:
        sums += t
        s = 0
    if i == n-2:
        sums += c
    t = c
print(sums)

Submission status: Accepted

Solution code:
n = int(input())
a = []
ans = 0
flag = True
for i in range(n):
    A = int(input())
    a.append(A)
next = 0
for i in range(n-1,-1,-1):
    if next - a[i] >= 2:
        flag = False
        break
    if a[i] == 0:
        next = 0
        continue
    if next - a[i] == 1:
        next = a[i]
        continue
    next = a[i]
    ans += a[i]
if a[0] != 0:
    flag = False
if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
if a[0] != 0:
    ans = -1
elif n == 1:
    ans = 0
else:
    b = a[1:]
    for k,i in enumerate(b):
        if i <= 1:
            ans += i
        else:
            num = i-a[k]
            if num == 1:
                ans += 1
            elif num <= 0:
                ans += i
            else:
                ans = -1
                break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

ans = 0

L = []
isok = True
for i in range(N):
    n = int(input())
    if n>i: isok = False
    L.append(n)

for i in range(N-1):
    if L[i+1] <= L[i]:
        ans += L[i+1]
    elif L[i+1] == L[i]+1:
        ans += 1
    elif L[i+1] > L[i]:
        isok=False
        break
    
if isok:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect, bisect_left

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

def reads():
  return [int(x) for x in input().split()]

N = read()

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

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

S = sorted(set(i - A[i] for i in range(N)))
print('S:', S, file=stderr)

ans = 0
for i in range(N):
  x = bisect_left(S, i) - bisect_left(S, i - A[i])
  print(i, x, file=stderr)
  ans += x
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())

start = int(input())
flag = 0
if start != 0:
 flag = 1
t = 0

for i in range(N-1):
 k = int(input())
 if k == start:
  t += start
 elif k == start + 1:
  t += 1
  start = k
 elif k == 0:
  start = 0
 elif k > start + 1:
  t = -1
  break
 else:
  t += k
  start = k

if flag ==1:
 t = -1
print(t)

Submission status: Accepted

Solution code:
def solve(n, aaa):
    if aaa[0] > 0:
        return -1
    if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])):
        return -1
    ans = 0
    a0 = 0

    for a1 in aaa[1:]:
        if a1 - a0 != 1:
            ans += a0
        a0 = a1

    return ans + a0


n = int(input())
aaa = list(map(int, (input() for _ in range(n))))
print(solve(n, aaa))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


@mt
def slv(N, A):

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

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

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


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

    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(1, n):
    diff = p[i] - p[i - 1]
    if diff >= 2:
        print(-1)
        exit()
    elif diff == 1:
        count += 1
    else:
        count += p[i]

print(count)

Submission status: Accepted

Solution code:
#!python
# -*- coding: utf-8 -*-


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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
#        print(n,a,ans,"case n dekai")
        break
#    print(M,a,"MA")
    if M > a:
        flag = 0
#        print(n,a,ans,"case n dekai")
        break
    M=max(M,a)
#    print(A,n,a,"A n a")
    
    if c == 0:
        ans+=a
#        print(a,"ans++")
    if n==0:
        break

    if a-1 == A[-1]:
#        print(A,a,ans,"kati")
        c=1
    else:
#        print(A,a,ans,"aiko")
        c=0

        

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# your code goes here
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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())

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
#! -*- coding: utf-8 -*-
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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=input()
last=-1
#q=[0]*n
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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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 #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# encoding:utf-8


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

	for val in values:
		#print(val, tmp ,cnt)
		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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:


import sys
#sys.stdin=open("data.txt")
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:
    # calculate answer
    ans=[0]*n
    for i in range(n):
        ans[i-a[i]]=a[i]
    print(sum(ans))

Submission status: Runtime Error

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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):
    if a[i+1] - a[i] > 1:
        print(-1)
        exit()
for _ in range(n):
    if set(a) == set([-1,0]) or set(a) == set([0]):
        break
    i = a.argmax()
    if i == 0:
        print(-1)
        exit()
    if a[i-1] + 1 == a[i]:
        a[i] = -1
        ans += 1
    elif a[i-1] == -1:
        a[i-1] = a[i] - 1
        a[i] = -1
        ans += 1
    else:
        print(-1)
        exit()
print(ans)

Submission status: Runtime Error

Solution code:
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

    # A[i] > iと、2以上大きくなるところがあるとダメ
    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
        for i in range(N - 1):
            if A[i] >= A[i+1]:
                ans += A[i]
        if A[-2] >= A[-1]:
            ans += A[-1]
        else:
            ans += 1

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

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
def solve():
  N = int(input())
  A = [int(input()) for _ in range(N)]
  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]>1:
      ans += 1
  return ans
print(solve())

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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

    if A[0] != 0:
        print(-1)
        return
    answer = 0
    for i in range(N - 1):
        if A[i + 1] - A[i] > 1:
            print(-1)
            return
        elif A[i + 1] == A[i]:
            answer += A[i]
        elif A[i + 1] == A[i] + 1:
            flag = A[i + 1]
        else:
            answer += flag
            flag = 0
    answer += flag
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
res=0
a1=int(input())
if a1!=0:
  print(-1)
  exit()
a2=int(input())
for  i in range(n-2):
  if a2-a1>1:
    print("-1")
    exit()
  if a2<=a1:
    res+=a1
  a1=a2
  a2=int(input())
if a2-a1>1:
    print("-1")
    exit()
if a2<=a1:
    res+=a1
res+=a2
print(res)

Submission status: Runtime Error

Solution code:
n=int(input())
res=0
a1=int(input())
if a1!=0:
  print(-1)
  exit()
a2=int(input())
for  i in range(n-2):
  if a2-a1>1:
    print("-1")
    exit()
  if a2<=a1:
    res+=a1
  a1=a2
  a2=int(input())
if a2-a1>1:
    print("-1")
    exit()
res+=a2
print(res)