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:
import sys

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

ans = 0
for i in range(n):
    if i == 0:
        if a[i] != 0:
            ans = -1
            break
    elif a[i] > i:
        ans = -1
        break

    else:

        if a[i] == a[i-1] + 1:
            continue
        else:
            ans += a[i-1]

for i in range(n-1):
    if a[i] == 0 and a[i+1] >= 2:
        ans = -1
if ans == -1:
    print(-1)
    sys.exit()

ans += a[n-1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

ans = 0
for i in range(n):
    if i == 0:
        if a[i] != 0:
            ans = -1
            break
    elif a[i] > i:
        ans = -1
        break

    else:

        if a[i] == a[i-1] + 1:
            continue
        else:
            ans += a[i-1]

if ans == -1:
    print(-1)
    sys.exit()

ans += a[n-1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

ans = 0
for i in range(n):
    if i == 0:
        if a[i] != 0:
            ans = -1
            break
    elif a[i] > i:
        ans = -1
        break

    else:

        if a[i] == a[i-1] + 1:
            continue
        else:
            ans += a[i-1]

if ans == -1:
    print(-1)
    sys.exit()

if a[n-1] == a[n-2] + 1:
    ans += a[n-1]

print(ans)

Submission status: Wrong Answer

Solution code:
#解説参照
import sys
n,*a,=map(int, sys.stdin.read().split())
if a[0]:
    print(-1)
    exit()

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

print(ans)

Submission status: Wrong Answer

Solution code:
#解説参照
import sys
n,*a,=map(int, sys.stdin.read().split())
if a[0]:
    print(-1)
    exit()

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,*a,=map(int, sys.stdin.read().split())
if a[0]:
    print(-1)
    exit()

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

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0))
r=-1
for i in range(n):
    if a[i-1] >= a[i]:r+=a[i]
    elif a[i-1]+1==a[i]:r+=1
    else:r=-1;break
print(r)

Submission status: Wrong Answer

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

n = int(input())
a = [int(input()) for _ in range(n)]
x = a[0]
ans = 0
if not x == 0:
    cannot()
a.reverse()
x = a[0]
cnt = 0
for i in range(n):
    if a[i] == 0:
        continue
    if a[i] < 0:
        cannot()
    if x == a[i]:
        cnt += 1
    else:
        if x - 1 == a[i] or x < a[i]:
            ans += x * cnt
            j = 0
            while True:
                if i + j >= n or j == x:
                    break
                a[i + j] -= (x - j - 1)
                j += 1
            x, cnt = a[i], 1
        else:
            cannot()
ans += x * cnt
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
i=N-1
l=[]
flag=1
ans=0
while i>0:
    if A[i]>i:
        flag=0
        break
    else:
        piv=A[i]
        ans=ans+piv
        #print("\n")
        #print(piv)
        while True:
            if (i-1>=0):
                if A[i-1]==piv-1:
                    i=i-1
                    piv=piv-1
                else:
                    break
            else:
                break
        i=i-1
        #print(i,ans)
        #input()
if flag==1:
    print(ans)
else:
    print("-1")

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
bn = int(input())
if not bn == 0:
    print(-1)
    exit()
for i in range(1,n):
    ai = int(input())
    if ai > i:
        print(-1)
        exit()
    elif ai == bn+1:
        ans += 1
    else:
        ans += ai
    bn = ai

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
bn = int(input())
if not bn == 0:
    print(-1)
    exit()
for i in range(n-1):
    ai = int(input())
    if ai <= bn:
        ans += ai
        bn = ai
        continue
    ans += (ai-bn)
    bn = ai

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

main()

Submission status: Wrong Answer

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

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

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

main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 reversed(range(1, n)):
    if A[i-1] >= A[i]-1:
        ans += 1
    else:
        ans += A[i]

print(ans)

Submission status: Wrong Answer

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

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

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

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

print(ans)

Submission status: Wrong Answer

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 reversed(range(1, n)):
    if A[i-1] >= A[i]-1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

print(-1)

Submission status: Wrong Answer

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

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

print(n-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

    return A[0][0] == 0

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

B = []
for a in A:
    B.extend(a)

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

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

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

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

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

    return A[0][0] == 0

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

ans = N - sum(grp.count(0) for grp in A) + len([0 for grp in A if grp[0] != 0])
print(ans)

Submission status: Wrong Answer

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

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

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

    return A[0][0] == 0

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

ans = N - sum(grp.count(0) for grp in A) + len([0 for grp in A if grp[0] != 0])
print(ans)

Submission status: Wrong Answer

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

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

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

if __name__ =='__main__':
    main()

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
if A[0]!=0:
  print(-1)
  exit()
for i in range(N-1):
  if A[i+1]-A[i]>1:
    print(-1)
    exit()
    
B=A[::-1]
cnt=0
for i in range(1,N):
  if B[i-1]==B[i]:
    cnt+=(B[i]-1)
print(N-A.count(0)+cnt)

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

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

ans += prev
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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



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

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

Submission status: Wrong Answer

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



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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
ans=0
##加工
left=0
while left<n:
    if A[left]==0 :
        left+=1
        continue
    right=left+1
    onajimoji=A[left]
    while right<n and A[right]==onajimoji: #rightを1つ進めてよいか確認
        right+=1
        ans+=onajimoji-1
    A[left:right]=[i for i in range(A[left],A[left]+right-left)]
    if left != right-1:
        left=right-1
        #もし書き換えていれば、1,1,1,1,4→1,2,3,4,4 みたいなケースがあるので、leftはright-1までなら飛ばしてよい
        continue
    left+=1
##加工終了

for i in range(n):
  if A[0]!=0:
    print(-1)
    exit()
    
  if i!=0:
    q=A[i]
    if q==A[i-1]+1:
      continue
    if A[i-1]>q:
      ans+=A[i-1]
      continue
    print(-1)
    exit()
print(ans+A[-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
  
##加工
left=0
while left<n:
    if A[left]==0 :
        left+=1
        continue
    right=left+1
    onajimoji=A[left]
    while right<n and A[right]==onajimoji: #rightを1つ進めてよいか確認
        right+=1
    A[left:right]=[i for i in range(A[left],A[left]+right-left)]
    if left != right-1:
        left=right-1
        #もし書き換えていれば、1,1,1,1,4→1,2,3,4,4 みたいなケースがあるので、leftはright-1までなら飛ばしてよい
        continue
    left+=1
##加工終了

ans=0

for i in range(n):
  if A[0]!=0:
    print(-1)
    exit()
    
  if i!=0:
    q=A[i]
    if q==A[i-1]+1:
      continue
    if A[i-1]>q:
      ans+=A[i-1]+q
      continue
    print(-1)
    exit()
print(ans+A[-1])

Submission status: Wrong Answer

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

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, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    # check
    idx = 0
    for i in range(N):
        if A[i] <= idx:
            if A[i] == 0:
                idx = 0
            idx += 1
            continue
        else:
            return print(-1)
        if i and A[i] - A[i-1] > 1:
            return print(-1)
    ma = 0
    ans = 0
    for a in A[::-1]:
        if a >= ma:
            ma = a
            ans += ma
        else:
            ma = a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    # check
    idx = 0
    for a in A:
        if a <= idx:
            if a == 0:
                idx = 0
            idx += 1
            continue
        else:
            return print(-1)
    ma = 0
    ans = 0
    for a in A[::-1]:
        if a >= ma:
            ma = a
            ans += ma
        else:
            ma = a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    return res

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

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

ans = 0
l = []

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

print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ans = 0
for i in range(N-1):
    if A[i+1]-A[i] > 1:
        ans = -1
        break
    if A[i] > i or A[i+1] > i+1:
        ans = -1
        break
        
if ans == 0:
    X = [0]*N
    for i in range(N-1, 0, -1):
        if A[i] > X[i]:
            ans += A[i]
            for j in range(A[i]):
                X[i-j] = A[i]-j
        elif X[i] > A[i]:
            ans = -1
            break
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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


def calc_depth(seq, pos):
    val = 1
    offset = seq[pos]
    depth = 0
    for i in range(pos, len(seq)):
        check_val = seq[i]
        if val <= check_val:
            depth += 1
            offset = min(check_val - val, offset)
            val += 1
        else:
            break
    return depth, offset


def update(seq, pos, depth, offset):
    return (
        seq[:pos] + [
            val - n - offset - 1 for n, val 
            in enumerate(seq[pos: (pos + depth)])
        ] + seq[(pos + depth):]
    )


def solve(N: int, A: "List[int]"):
    if A[0] > 0:
        print(-1)
        return
    score = 0
    for pos in range(len(A)):
        depth, offset = calc_depth(A, pos)
        if not depth:
            continue
        score += depth + offset
        A = update(A, pos, depth, offset)
    print(score)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

N, = map(int, input().split())
L = [int(input()) for _ 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()

a = []
b = []
t = 0
for i in range(N):
    if L[i] == t:
        t += 1
        b.append(i)
        continue

    if L[i] == 0:
        a.append(b)
        b = [i]
        t = 1
        continue

    if L[i] == 1:
        a.append(b)
        b = [i]
        t = 2
        continue

    a.append(b)
    b = [i]
    a.append(b)
    b = []
    t = 1

if len(b) != 0:
    a.append(b)

ans = 0
for v in a:
    a = 0
    for i in v:
        a = max(a, L[i])
    ans += a
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

N, = map(int, input().split())
L = [int(input()) for _ in range(N)]

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

a = []
b = []
t = 0
for i in range(N):
    if L[i] == t:
        t += 1
        b.append(i)
        continue

    if L[i] == 0:
        a.append(b)
        b = [i]
        t = 1
        continue

    if L[i] == 1:
        a.append(b)
        b = [i]
        t = 2
        continue

    a.append(b)
    b = [i]
    a.append(b)
    b = []
    t = 1

if len(b) != 0:
    a.append(b)

ans = 0
for v in a:
    a = 0
    for i in v:
        a = max(a, L[i])
    ans += a
print(ans)

Submission status: Wrong Answer

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 and A[N-1]==A[N-2]+1:
        cnt += A[N-1]
print(cnt)