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: Time Limit Exceeded

Solution code:
n=input()
p=[]
q=[0]*n
ans=0
for i in range(n):
    p.append(input())
for i in range(n-1,-1,-1):
    if p[i]>q[i]:
        if p[i]>i:
            print -1
            break
        for j in range(i-p[i]+1,i+1):
            q[j]=q[j-1]+1
            ans+=1
    elif p[i]<q[i]:
        print -1
        break
else:
    print ans

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N = int(input())

pre = int(input())
if pre != 0:
    print(-1)
    sys.exit()
ans = 0
for _ in range(N-1):
    x = int(input())
    if pre + 1 < x:
        print(-1)
        sys.exit()
    elif pre + 1 == x:
        ans += 1
    else:
        ans += x
    pre = x

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin=sys.stdin

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()

n=ip()
ans=[]
a=[-1]
out=0
now_max=0

for i in range(n):
  s=ip()
  if a[-1]+2<=s:
    out+=1
    break
  elif a[-1]>s:
    ans.append(now_max)
    now_max=s
    if i==n-1:
      ans.append(now_max)
  elif a[-1]==s:
    ans.append(now_max)
    if i==n-1:
      ans.append(now_max)
  elif a[-1]+1==s:
    now_max=s
    if i==n-1:
      ans.append(now_max)
  a.append(s)
      
if out==0:
  print(sum(ans))
else:
  print(-1)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	n=II()
	A=[II() for _ in range(n)]+[0]


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

	ans=0

	for i,j in zip(A[:-1],A[1:]):
		if j-i>=2:
			print(-1)
			exit()
		elif j-i<=0:
			ans+=i

	print(ans)












if __name__ == "__main__":
	main()

Submission status: Accepted

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

N = int(input())
G = [[]]
A = []

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

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

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

ans = 0
A = [-10**18] + A[::-1]

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

Submission status: Accepted

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


N, *A = map(int, open(0).read().split())
if A[0] != 0:
    terminate()

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inp() for _ in range(n)]
res = 0
for i in range(1,n)[::-1]:
    if a[i]-a[i-1] == 1:
        res += 1
    else:
        res += a[i]
for i in range(n-1):
    if a[i+1] - a[i] > 1:
        res = -1
if a[0] != 0:
    res = -1 
print(res)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
# 状態1: iとi+1が1違う
# 状態2: iとi+1が同じ
# これ以外のiとi+1の関係があったら構築できない

# 状態1ではi+1を作る過程でiも作れる。
# 状態2ではi+1を作った後にiを作る必要がある。
# 後ろから見てa[i] - 1 == a[i - 1]となってる数を数えなければおｋ

# check
if a[0] != 0:
	print(-1)
	exit()
for i in range(n - 1):
	if a[i + 1] - a[i] > 1:
		print(-1)
		exit()

# count
i = n - 1
ans = 0
while i > 0:
	ans += a[i]
	while i > 0 and a[i] - 1 == a[i - 1]:
		i -= 1
	i -= 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
flag = 0
cnt = A[N-1]
for i in range(N-2,-1,-1):
    if A[i]==A[i+1]-1:continue
    elif A[i]>=A[i+1]:
        if A[i]>0:
            cnt += A[i]
    else:
        flag = 1
        break
if A[0]>0 or flag==1:
    print(-1)
else:
    print(cnt)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())

# hantei
ok = True
for i in range(n - 1):
    if a[i + 1] - a[i] > 1:
        ok = False
if not ok or a[0] != 0:
    print(-1)
    exit()


ans = 0
a = list(reversed(a))
i = 0
while i < n:
    ans += a[i]
    while i < n - 1 and a[i] - 1 == a[i + 1]:
        i += 1
    i += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

f=True
t=0
c=0
for i in a:
  if i==t:
    t-=1
  elif i<t:
    f=False
    break
  else:
    t=i-1
    c+=i
if t!=-1:
  f=False
print(c if f else -1)

Submission status: Accepted

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

def main(N, A):
    if A[0] != 0: return -1
    if any([A[i+1] - A[i] > 1 for i in range(N-1)]): return -1
    A.reverse()
    ans = 0
    before = -1
    for a in A:
        if a+1 != before:
            ans += a
        before = a
    return ans

print(main(N, A))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

cnt=0
for i in range(1,n):
    if A[i-1]+1==A[i]:
        cnt +=1
    elif A[i-1]==A[i] or A[i-1]>A[i]:
        cnt +=A[i]
    else:print(-1);exit()

print(cnt)

Submission status: Accepted

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

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

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

print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
a = [int(input()) for i in range(n)]
if a[0] != 0:
    ans = -1
    

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

Submission status: Accepted

Solution code:
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
A.append(0)
if A[0]!=0:
    print(-1)
    exit()
a0 = 0
res = 0
for a in A:
    if a0 >= a:
        res += a0
    elif a - a0 >= 2:
        print(-1)
        exit()
    a0 = a
print(res)

Submission status: Accepted

Solution code:

N = int(input())

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

res = 0
last = N
for i,a in zip(reversed(range(N)), reversed(A)):
    j = i-a
    if j > last or j < 0:
        res = -1
        break
    elif j < last:
        last = j
        res += a

print(res)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(a):
    if a[0][0] != 0:
        return -1
    res = 0
    for aa in a:
        for i in range(len(aa)):
            if i == 0:
                res += aa[i]
            elif aa[i - 1] + 1 == aa[i]:
                res += 1
            elif aa[i - 1] == aa[i]:
                res += aa[i]
            else:
                return -1
    return res


def main():
    n = int(input())
    a = [[]]
    last_a = 0
    for _ in range(n):
        now = int(input())
        if last_a > now:
            a.append([])
        a[-1].append(now)
        last_a = now
    print(solve(a))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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
        if N == 1:
            ans = 0
        else:
            for i in range(N - 1):
                if A[i] >= A[i+1]:
                    ans += A[i]
            ans += A[-1]

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    lis=LI2()
    ind=[i for i in range(n)]
    if lis[0]!=0:
        print(-1)
        sys.exit()
    for i in range(1,n):
        if lis[i]==0:
            ind[i]=0
        else:
            ind[i]=ind[i-1]+1
    for i in range(n):
        if lis[i]>ind[i]:
            print(-1)
            sys.exit()
    ans=0
    for i in range(n-1):
        x=lis[i]
        if lis[i+1]==lis[i]+1:
            continue
        elif lis[i+1]>lis[i]+1:
            print(-1)
            sys.exit()
        else:
            ans+=x
    if n!=1 and lis[-1]==lis[-2]+1:
        ans+=lis[-1]
    else:
        ans+=lis[-1]
    
    print(ans)
            
            
            
            
        
    
    
    
    



if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    ans = 0
    prev_a = -1
    for i, a in enumerate(A):
        if (a > i) or (a > prev_a + 1):
            ans = -1
            break

        if a > 0:
            ans += 1
            if prev_a + 1 != a:
                ans += (a - 1)

        prev_a = a

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    a_ = int(input())
    if a_ != 0:
        print(-1)
        return True
    for n in range(N-1):
        a = int(input())
        if a - a_ > 1:
            print(-1)
            return True
        if a - a_ == 1:
            ans += 1
            a_ = a
        else:
            ans += a
            a_ = a
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
ans = -1
prev = -1
for _ in range(n):
    a = int(input())
    if prev+1 == a:
        prev = a
        ans += 1
        continue
    if prev+1 < a:
        print(-1)
        break
    ans += a
    prev = a
else:
    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 = A[-1]
for a, prev_a in reversed(tuple(zip(A, A[1:]))):
    if a == prev_a-1:
        continue
    if a < prev_a-1:
        print(-1)
        break
    ans += a
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
cnt = 0
#-A1がマイナスならXと同じにならない-#
a1 = int(input())
if a1 != 0:
    print(-1)
#-A1<A2=A1+1なら+1,それ以外なら-1#
else:
    before = a1
    for i in range(1,N):
        a1 = int(input())
        if a1 == 0:
            continue
        elif a1==before+1:
            cnt += 1
        elif a1 <= before:
            cnt += a1
        else:
            print(-1)
            exit()
        before = a1
    print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = [ni() for _ in range(n)]
    ans = 0

    prev = -1
    for i, ai in enumerate(reversed(a)):
        if ai > n - i - 1:
            print(-1)
            exit(0)

        if i == 0:
            ans += ai
        else:
            if ai != prev - 1:
                if ai > prev - 1:
                    ans += ai
                else:
                    print(-1)
                    exit(0)
        prev = ai
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = [ni() for _ in range(n)]
    ans = 0

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

    prev = -1
    for i, ai in enumerate(reversed(a)):
        if ai > n - i - 1:
            print(-1)
            exit(0)

        if i == 0:
            ans += ai
        else:
            if ai != prev - 1:
                if ai > prev - 1:
                    ans += ai
                else:
                    print(-1)
                    exit(0)
        prev = ai
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

a=[int(input()) for _ in range(n)]
#a(n+1)!=0の時、a(n+1)=a(n)+1である

cnt=0

if a[0]!=0:
    print(-1)
    exit()
#print(" ".join(list(map(str,a))))
for ii in range(1,n):
    i=n-ii
    if a[i]==0:
        continue
    elif a[i]<=a[i-1]:
        cnt+=a[i]
    elif a[i]==a[i-1]+1:
        cnt+=1
    elif a[i]>a[i-1]+1 or  a[i]>i:
        print(-1)
        exit()
    #print(b)
    #print(" "*(i+1),"^",cnt)

print(cnt)

    
"""
t: 0 1 1 0 1 2 2 1 2
s: 0 0 0 0 0 0 0 0 0
1: 0 0 1 0 0 0 0 0 0
2: 0 1 1 0 0 0 0 0 0
3: 0 1 1 0 0 0 0 1 0
4: 0 1 1 0 0 0 0 1 2
5: 0 1 1 0 0 1 0 1 2

"""

Submission status: Accepted

Solution code:
n = int(input())
alst = [int(input()) for _ in range(n)]
ans = 0
bef = 0
if alst[0] != 0:
    print(-1)
    exit()
    
for num in alst[1:]:
    if num == bef + 1:
        pass
    elif num > bef + 1:
        print(-1)
        exit()
    else:
        ans += bef
    bef = num
ans += bef
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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 TUPLE(): return tuple(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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

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

print(cnt)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 TUPLE(): return tuple(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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

ans = 0
tmp = A[0]
for i, a in enumerate(A):
	if i < a or tmp+1 < a:
		print(-1)
		break
	if a != tmp+1:
		ans += tmp
	tmp = a

else:
	ans += tmp
	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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 TUPLE(): return tuple(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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

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

print(cnt)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    A = []
    for _ in range(n):
        A.append(int(input()))
    mae = -1
    ans = -1
    for AA in A:
        if AA > mae+1:
            print(-1)
            break
        elif AA == mae+1:
            ans += 1
        else:
            ans += AA
        mae = AA
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[I() for _ in range(n)]

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

  ans=0
  st=l[0]
  for x in l[1:]:
    if st+1<x:
      return -1

    if x==st:
      ans+=x

    elif st<x:
      ans+=1

    elif st>x:
      ans+=x

    st=x

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    if A[0] > 0:
        print(-1)
        return
    for n in range(N - 1):
        if  A[n + 1] >= A[n] + 2:
            print(-1)
            return
    # 後ろから見ていく。前項以上なら加算、前項未満なら加算せず。
    A = A[::-1]
    ans = A[0]
    for n in range(N - 1):
        if A[n + 1] >= A[n]:
            ans += A[n + 1]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

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

    ans = 0
    for a, b in zip(A[0:], A[1:]):
        if b - a >= 2:
            print(-1)
            return
        elif b - a == 1 or (a == 1 and a == b):
            ans += 1
        else:
            ans += b

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

    # KeyInsight:
    # ◯: 2マスの値を比べる。
    #    右側 - 左側 = 1のときは、答えに1加算。
    #    同じ値のときは、その値を答えに加算。
    # ◯: a0以外のときと、2マスの差が2以上のときは、条件を満たさない。
    # △: 上記の考察を実装したが、10ケースWA。
    # △: 条件を満たさない場合を先に持ってくると、その後の条件がシンプルに。

    # See:
    # https://atcoder.jp/contests/agc024/submissions/15705631
    for pre, cur in zip(a, a[1:]):
        if pre + 1 < cur:
            print(-1)
            exit()

        if pre + 1 == cur:
            ans += 1
        else:
            ans += cur

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])

    def search(self, s, g):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]



def solve():
    n = getN()
    nums = []
    for i in range(n):
        nums.append(getN())
    # for i, num in nums:
    #     if num > i + 1:
    #         print(-1)
    #         return
    # nums.reverse()
    # next = nums[0]
    # ans = 0
    # if next != 0:
    #     ans += 1
    #
    # for num in nums[1:]:
    #     if next != 0:
    #         ans +=
    if nums[0] != 0:
        print(-1)
        return
    prev = 0
    ans = 0
    for num in nums[1:]:
        if num > prev + 1:
            print(-1)
            return
        if num == prev + 1:
            ans += 1
        if num<= prev:
            ans += num
        prev = num
    print(ans)
    return
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    if A[0] > 0:
        print(-1)
        return
    ans = 0
    for i in range(1,N):
        # print(i, A[i])
        if A[i] == 0:
            continue
        if A[i] == 1:
            ans += 1
            continue
        if A[i] == A[i-1]+1:
            ans += 1
            continue
        if A[i] <= A[i-1]:
            ans += A[i]
            continue
        print(-1)
        return
    print(ans)
if __name__ == '__main__':
    main()