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: Wrong Answer

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

if A[0] != 0 or any(l + 1 < r for l, r in zip(A, A[1:])):
    print(-1)
    exit()

ans = 0
for l, r in zip(A, A[1:]):
    if l <= r:
        ans += 1
    elif r > 0:
        ans += 2

print(ans)

Submission status: Wrong Answer

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

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

if A[0] != 0 or any(l + 1 < r for l, r in zip(A, A[1:])):
    print(-1)

ans = 0
for l, r in zip(A, A[1:]):
    if l <= r:
        ans += 1
    elif r > 0:
        ans += 2

print(ans)

Submission status: Wrong Answer

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] not in (0, 1, A[i], A[i] + 1):
        terminate()
    if A[i] + 1 == A[i + 1] or A[i + 1] == 1:
        ans += 1
    elif A[i] == A[i + 1]:
        ans += A[i]
print(ans)

Submission status: Wrong Answer

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]
if a[0] != 0:
    res = -1 
print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 or (a[i] > a[i + 1] and a[i + 1] > 1):
        ok = False
if not ok or a[0] != 0:
    print(-1)
    exit()

# 1以下始まり、非単調増加で差が1以下なら行ける
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: Wrong Answer

Solution code:
c=g=p=e=0
for i in range(int(input())):
    if not e:
        if (a:=int(input()))>i:e=1
        else:
            if i!=0:(g,c,p)=(g+1,c+1,a) if a==p+1 else (g+a,0,a)
print(-1 if e else g)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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:
        frag = True
    elif tmp != a[i]:
        ans += a[i]
    tmp = max(a[i] - 1, 0)
else:
    print(-1 if flag else ans)

Submission status: Wrong Answer

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:
        frag = False
    elif tmp != a[i]:
        ans += a[i]
    tmp = max(a[i] - 1, 0)
else:
    print(-1 if flag else ans)

Submission status: Wrong Answer

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]:
                pass
            else:
                ans = -1
                break
print(ans)

Submission status: Wrong Answer

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] == 0:
                pass
            else:
                ans = -1
                break
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from copy import *
n = int(input())
a = [int(input()) for _ in range(n)]
tmp = deepcopy(a)
ans = 0
for _ in range(n):
    i = a.index(max(a))
    if a[i-1] + 1 == a[i]:
        a[i] = -1
        tmp[i] = 0
        ans += 1
    elif a[i-1] == -1:
        a[i-1] = a[i] - 1
        a[i] = -1
        tmp[i] = 0
        ans += 1
    else:
        print(-1)
        exit()
    if sum(tmp) == 0:
        break
print(ans)

Submission status: Wrong Answer

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 = 1
        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: Wrong Answer

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

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

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

    ans = len([i for i in A if i > 0])
    if is_ok:
        # A[i] >= A[i+1] >= 2のとき、余計に1手
        for i in range(N - 1):
            if A[i] >= A[i+1] >= 2:
                ans += 1

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

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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[0]!=0か、A[i]+1 < A[i+1]があるとダメ
    if A[0] != 0:
        is_ok = False
    else:
        for i in range(N - 1):
            if A[i] + 1 < A[i+1]:
                is_ok = False
                break

    ans = len([i for i in A if i > 0])
    if is_ok:
        # A[i] >= A[i+1] >= 2のとき、余計に1手
        for i in range(N - 1):
            if A[i] >= A[i+1] >= 2:
                ans += 1

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

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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]
    print(ans)
            
            
            
            
        
    
    
    
    



if __name__=="__main__":
    main()

Submission status: Wrong Answer

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
    mem=0
    '''for i in range(n):
        j=n-i-1
        u=lis[j]
        if lis[j-1]!=lis[j]-1:
            ans+=u
            ans+=mem
            mem=0
        else:
            mem=lis[j]'''
    for i in range(n-1):
        x=lis[i]
        if lis[i+1]==lis[i]+1:
            continue
        else:
            ans+=x
    if n!=1 and lis[-1]==lis[-2]+1:
        ans+=lis[-1]
    print(ans)
            
            
            
            
        
    
    
    
    



if __name__=="__main__":
    main()

Submission status: Wrong Answer

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 a == prev_a:
                ans += (a - 1)

        prev_a = a

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())

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

ans=0
temp=0
f=0
for i in range(N-1):
    A=int(input())
    if A-A0>1:
        print(-1)
        exit()
    if A == 0:
        if f==0:
            temp=temp-A0+1
        ans += temp
        temp = 0
        f=0
    elif A==A0:
        temp+=A
        f+=1
    elif A<A0:
        temp=temp-A0+1
        temp+=A
        f=0
    else:
        temp+=A
        f=0

    A0=A

ans+=temp
if f==0:
    ans=ans-A0+1

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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 tmp != A[i]:
		cnt += A[i]
		tmp = A[i]

print(cnt)

Submission status: Wrong Answer

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 abs(st-x)>1:
      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: Wrong Answer

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

    for pre, cur in zip(a, a[1:]):
        if cur <= 1 and (pre > cur):
            ans += cur
            continue

        if (cur - pre) == 1:
            ans += 1
        elif cur == pre:
            ans += cur
        else:
            print(-1)
            exit()

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    for pre, cur in zip(a, a[1:]):
        if cur <= 1 and (pre > cur):
            ans += cur
            pre = cur
            continue

        if (cur - pre) == 1:
            ans += 1
        elif cur == pre:
            ans += cur
        else:
            print(-1)
            exit()

        pre = cur

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
  N = int(input())
  A = [int(input()) for _ in range(N)]
  if N==1:
    if A[0]==0:
      return 0
    return -1
  if A[0]>0 or A[1]>1:
    return -1
  ans = N - A.count(0)
  for i in range(1,N-1):
    if A[i]+1<A[i+1]:
      return -1
    if A[i]>=A[i+1] and A[i+1]>1:
      ans += 1
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
n = int(input())
As = [int(input()) for i in range(n)]
dp  = [0] * n #どこまで伸ばせたか
mx = 0
for i,a in enumerate(As):
    if a == 0:continue
    if i - a < mx: #遡ってしまったら
        print(-1)
        exit()
    else:
        dp[i-a] = a
        mx = i-a

print(sum(dp))

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
a = [[i,ir()] for i in range(n)]
a.reverse()
pre = -1
ans = 0
for ind, num in a:
    if num <= ind:
        if pre-1 != num:
            ans+=num
            pre = num
        else:
            # nice
            pre = num
    else:
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    if A[0] != 0:
        print(-1)
        exit()
    B = [0] * N
    for i in range(N):
        if 0 <= i - A[i] <= i:
            B[i] = i - A[i]
        else:
            print(-1)
            exit()
    
    pre = max(B)
    cnt = len(B) - 1 - pre
    for i in range(N-1,-1,-1):
        if B[i] != pre:
            cnt += i - B[i]
            pre = B[i]
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    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] <= A[i-1] + 1:
            cnt += 1
        elif A[i] > A[i-1] + 1:
            cnt += A[i] - A[i-1]

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    nw = -1
    ret = 0
    for i, a in enumerate(A):
        if i<a:
            print(-1)
            exit()
        elif i == 0:
            nw = 0
            continue
        elif nw+1==a:
            nw += 1
            continue
        else:
            ret += nw
            nw = a
    ret += a
#            print(i,ret)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    for i, a in enumerate(A):
        if i<a:
            print(-1)
            exit()
    A = A[::-1]
    ret = A[0]
    nw = A[0]
    for a in A[1:]:
        if a == nw -1:
            nw = a
            continue
        else:
            ret += a
            nw = a
#            print(i,ret)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    if A[0] != 0:
        print(-1)
        exit()
    else:
        A = A[::-1]
        ret = A[0]
        nw = A[0]

        for i, a in enumerate(A[1:]):
            if a == nw -1:
                nw = a
                continue
            else:
                ret += a
                nw = a
#            print(i,ret)
        print(ret)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
  temp = int(input())
  A.append(temp)
if A[0] != 0:
  print(-1)
  exit()
ans = 0
prev = 0

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  la = [int(input()) for _ in range(n)]
  cnt = 0
  for i in range(n):
    if la[i] > i:
      print(-1)
      return
    
    if i+1 < n and la[i]+1 == la[i+1]:
      continue
    else:
      cnt += la[i]
  print(cnt)
    
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
now = int(input())
if now != 0:
    print(-1)
    exit()

for i in range(n-1):
    a = int(input())
    if a == now or a == now + 2:
        ans += a
        now = a
    elif a == now + 1:
        ans += 1
        now = a
    elif a == 1:
        ans += 1
        now = 1
    elif a == 0:
        now = 0
    else:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
now = int(input())
if now != 0:
    print(-1)
    exit()

for i in range(n-1):
    a = int(input())
    if a == now:
        ans += a
        now = a
    elif a == now + 1:
        ans += 1
        now = a
    elif a >= now + 2:
        print(-1)
        exit()
    elif a == 1:
        ans += 1
        now = 1
    elif a == 0:
        now = 0
    else:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

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

ans = 0
if A[0] != 0:
  ans = -1
else:
  pre = 0
  for i in range(1,n):
    if A[i] == pre+1:
      ans += 1
      pre += 1
    elif A[i] == pre:
      ans += A[i]
    elif A[i] == pre-1:
      ans += A[i]
      pre -= 1
    else:
      ans = -1      
      break
      
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

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


def solve():
    c = 0
    ans = 0
    for i in range(N - 1, -1, -1):
        s = A[i]
        if s > i:
            return -1
        if s < c:
            return -1
        ans += s - c
        c = s - 1
    return ans


print(solve())

Submission status: Wrong Answer

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

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

for a in A[::-1]:
    now -= 1
    if a > now:
        ans += a - now
        now = a
    elif a < now:
        ans = -1
        break

print(ans)

Submission status: Wrong Answer

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

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

cnt,length=0,0
for i in range(n-1):
    if A[i]!=0:length +=1
    else:length=0

    if A[i]<=length:
        if A[i]+1==A[i+1]:cnt +=1
        elif abs(A[i]-A[i+1])>1:print(-1);exit()
        else:cnt +=A[i+1]
    else:print(-1);exit()
print(cnt)

Submission status: Wrong Answer

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

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

cnt,length=0,0
for i in range(n-1):
    if A[i]!=0:length +=1
    else:length=0

    if A[i]<=length:
        if abs(A[i]-A[i+1])>1:print(-1);exit()
        elif A[i]+1==A[i+1]:cnt +=1
        else:cnt +=A[i+1]
    else:print(-1);exit()
print(cnt)

Submission status: Wrong Answer

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

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

cnt,length=0,0
for i in range(n-1):
    if A[i]!=0:length +=1
    else:length=0

    if A[i]<=length:
        if A[i]+1==A[i+1]:cnt +=1
        else:cnt +=A[i+1]
    else:print(-1);exit()
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
    else:cnt +=A[i]
print(cnt)