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:
# 0, 1, 2, 3, ... の重ね合わせで書けるかどうか。多分。証明してないけど。

n = int(input())

nums = [int(input()) for i 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()
    elif nums[i] == nums[i-1] + 1:
        # 直前と同じ山に含まれる
        ans += 1
    else:
        # 直前とは違う、新たな山を作る必要がある
        ans += nums[i]

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = MI(N,1)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np
N = int(input())
A = np.array([int(input()) for _ in range(N)] + [0], dtype=np.int64)
# print(A)
ans = (A[:-1][A[:-1] >= A[1:]]).sum()
if any(A[:-1] + 1 < A[1:]):
    ans = -1
elif A[0] != 0:
    ans = -1

print(ans)

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)
        # print(i,A[i],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(i,ans)
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
x=[0]*(n+1)
a=[int(input()) for _ 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()
res=0
for i in range(1,n):
  if a[i]==a[i-1]+1:
    res+=1
  else:
    res+=a[i]
print(res)

Submission status: Accepted

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

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

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

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(N-1,0,-1):
    l,a=A[i-1],A[i]
    if a>l+1:
        print(-1)
        exit()
    elif a==l+1:
        ans+=1
    elif a!=0:
        ans+=a
print(ans)

Submission status: Accepted

Solution code:
#N, *a = map(int, open(0).read().split())
N = int(input())
a=[]
for i in range(N):
    a.append(int(input()))

def main():
    flag = 0
    tmp = a[-1]
    ans = 0
    
    for aa in reversed(a[:-1]):
        if aa >= tmp:
            ans += tmp
            tmp = aa
        elif aa +1 == tmp:
            ans += 1
            tmp = aa
        else:
            return -1

    if a[0] != 0:
        ans = -1
    return ans
            
print(main())

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
c=[int(input())for i in range(n)]
d=0
p=0
for i in range(n-1,0,-1):
    if c[i]-c[i-1]>1:
        print(-1)
        break
    else:
        if d!=c[i]:
            p+=c[i]
            d=c[i]
    d-=1
else:
    print(-1if c[0]>0else p)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST(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:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
  l.append(int(input()))
#増えるとしたら1,2,3..のように増加分は1ずつ
#減るとしたらnumになるとして、一つ前をnum-1にする!
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
  #print(i, res)
if x > 0: res += (s - 1) * x + 1
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# MOD = 998244353

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

# 最初が0じゃないとだめ
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#Sequence Growing Easy

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

Submission status: Accepted

Solution code:
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(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#ライブラリインポート
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()

Submission status: Accepted

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

# 単調非減少
# 差分は0/1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AGC024C - Sequence Growing Easy
def main():
    N, *A = map(int, open(0))
    if A[0]:  # can't increment A_0
        print(-1)
        return
    A.append(0)
    ans, B = 0, A[::-1]
    for i, j in zip(B, B[1:]):  # check from the last
        if i > j + 1:  # increment from left one must be 0 or 1
            print(-1)
            return
        if j >= i:  # left one is an end of subsequence
            ans += j
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC024C - Sequence Growing Easy
def main():
    N, *A = map(int, open(0))
    A.append(0)
    if A[0]:  # corner case
        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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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