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:
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    f = True
    ans = 0
    L = n-1
    for i in reversed(range(n)):
        if i < a[i] or a[i] < i-L:
            f = False
            break
        if i-L < a[i]:
            ans += a[i]
            L = i - a[i]
    if f:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
sts = dict()
mi = 0
bl = 0

for i in range(n):
    ai = int(input())
    if i-ai >= mi:
        sts[i-ai] = ai
        if bl >= ai:
            mi = i-ai
    else:
        print(-1)
        exit()
    bl = ai

for i in sts.values():
    ans += i
print(ans)

Submission status: Accepted

Solution code:
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] > a[i-1] + 1:
    ans = -1
    break
  if a[i] == a[i-1] + 1:
    ans += 1
  else:
    ans += a[i]
    
print(ans)

Submission status: Accepted

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

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

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

tmp = 0
ans = 0
for i in range(1,N):
    if A[i] < tmp+1:
        ans += tmp
    tmp = A[i]

ans += tmp

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=t=-1
for i in range(N):
 A=int(input())
 if t+1<A:
  a=-1
  break
 if t+1==A:a+=1
 else:a+=A
 t=A
print(a)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    if A[0]!=0:
        print(-1)
        sys.exit()
    dp=[0]*n
    for i,a in enumerate(A[1:],1):
        if a>=A[i-1]+2:
            print(-1) 
            sys.exit()
        elif a==A[i-1]+1:
            dp[i]=1
        else:
            dp[i]=a
    print(sum(dp))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
a=-1
t=-1
for i in range(N):
    A=int(input())
    if t+1<A:
        a=-1
        break
    if t+1==A:
        a+=1
    else:
        a+=A
    t=A
print(a)

Submission status: Accepted

Solution code:
N = int(input())
c = 0
A = []
for i in range(N):
  a = int(input())
  if a > i:
    c = 1
  if i >=1 and a > A[i-1]+1:
    c = 1
  A.append(a)

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

Submission status: Accepted

Solution code:
#sequence growing easy
N=int(input())
a=[int(input()) for _ in range(N)]
answer=0
now_value=10**9
for i in range(N-1,-1,-1):
    if a[i]>i:
        answer=-1
        break 
    if a[i]==now_value-1:
        now_value-=1
    else:
        answer+=a[i]
        now_value=a[i]
for i in range(N-1):
    if a[i+1]-a[i]>1:
         answer=-1
         break
print(answer)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

'''MEMO:
うしろから見ていく。
0なら、一つ前が0,1なら次へ。
高さhのとき：
    そのますもふくめて前にh+1ますなければ：-1
    あれば：+h回の操作
        次のますがh-1となっているか？
        なっていれば：さらに次
        なっていなければ：はじめから
'''

def main(): 
    N = II()
    A = []
    for i in range(N):
        A.append((i, II()))
    
    action = 0
    prev_h = 0
    for i, h in reversed(A):
        if h == 0:
            if prev_h <= 1:
                pass
            else:
                print(-1)
                return
        else:
            if i < h:
                print(-1)
                return
            else:
                if prev_h == 0 or prev_h < h+1:
                    action += h
                elif prev_h > h+1:
                    print(-1)
                    return
                else:
                    pass
        prev_h = h
    print(action)



main()

Submission status: Accepted

Solution code:
# AGC024C

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


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

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

Submission status: Accepted

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

def main():
    cur = 0
    ans = 0

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

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

    print(ans)

    
main()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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(1, n):
    if A[i] > A[i-1]+1:
        print(-1)
        exit()

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

print (count)

Submission status: Accepted

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

for _ in range(N):
    a = int(input())
    if len(A[-1]) > 0 and a < A[-1][-1]:
        A.append([])
    A[-1].append(a)

def isOk():
    for l, r in zip(A, A[1:]):
        if l[-1] + 1 < r[0]:
            return False
    for grp in A:
        for l, r in zip(grp, grp[1:]):
            if l + 1 < r:
                return False

    return A[0][0] == 0

if not isOk():
    print(-1)
    exit()

B = []
for a in A:
    B.extend(a)
B = [-10**18] + B[::-1]

ans = 0
for r, l in zip(B, B[1:]):
    if l >= r:
        ans += l
print(ans)

Submission status: Accepted

Solution code:
# 最初は0から始まる
# その次は、今の数+1以下である必要がある。
# 今の数+2以上が現れたらNG
# 通常は（0以外のときに）ans += 1
# 同じ数以下のとき、たとえば5 -> 3となっているときは、
# それまでに3を作れているはずなので、3を足す

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

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
import sys

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

MOD = 1000000007

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

if __name__ =='__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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



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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())

ans = -1

tmp = -1

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

print(ans)

Submission status: Accepted

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

ans = 0

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

Submission status: Accepted

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

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

else:
	ans += tmp
	print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


from functools import *
import sys

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


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


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




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


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

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

count = 0
x = [0]*N

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

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

 """
print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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


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


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


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


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

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

print(ans+pre*count)

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

    return res

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

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

ans = 0
l = []

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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

Submission status: Accepted

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(1, N):
    if A[i] - A[i-1] > 1:  # 前の数に+1することでしか数を生成することができないため、2以上離れている場合は無理
        print(-1)
        exit()

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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