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

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

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = -1
tmp = -1 #直前の数字
for i in range(N):
    A = int(input())
    if A > i:
        print (-1)
        exit()
    if tmp + 1 == A:
        ans += 1
        tmp += 1
    else:
        ans += A
        tmp = A

print (ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
B = []
if A[0] != 0:
  p = -1
else:
  p = 0
for i in range(1, N):
  if A[i] - A[i-1] > 2:
    p = -1
  elif A[i] - A[i-1] <= 0:
    B.append(i-1)
if p == -1:
  print(p)
else:
  print(sum(A[B[i]] for i in range(len(B))) + A[N-1])

Submission status: Wrong Answer

Solution code:
def main(n, A):
    if A[0] != 0:
        return - 1

    res = 0
    for x, y in zip(A[:-1], A[1:]):
        if x >= y:
            res += y
        else:
            res += y - x
    return res


if __name__ == "__main__":
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = main(n, a)
    print(ans)

Submission status: Wrong Answer

Solution code:
def main(n, A):
    if A[0] != 0:
        return -1

    res = 0
    for i in range(n):
        if i == 0:
            left = 0
            continue

        a = A[i]
        if left < a:
            res += a - left
        else:
            res += a
        left = a
    return res


if __name__ == "__main__":
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = main(n, a)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n = int(sys.stdin.readline().strip())
a_ls = []
for i in range(n):
    a = int(sys.stdin.readline().strip())
    a_ls.append(a)

if a_ls[0] != 0:
    print(-1)
else:
    cur = a_ls[-1]
    res = cur
    for a in a_ls[::-1][1:]:
        cur -= 1
        if a - cur > 0:
            res += a - cur
            cur = a
        elif a == cur:
            continue
        else:
            res = -1
            break
    print(res)

Submission status: Wrong Answer

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

flag = (A[0] == 0)
ans = 0

for i in range(1, N):
    d = A[i] - A[i - 1]
    if d == 1:
        ans += 1
    elif d == 0:
        ans += A[i]
    elif A[i] == 0:
        pass
    elif A[i] == 1:
        ans += 1
    else:
        flag = False
        break

if flag is False:
    ans = -1

print(ans)

Submission status: Wrong Answer

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

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

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

  ret = 0
  for i in range(1, N) :
    if A[i] == 0 :
      continue

    ret += 1
    if A[i] != A[i-1] + 1 :
      ret += A[i] - 1
  
  return ret

print(solve())

Submission status: Wrong Answer

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

def solve() :
  now = 0
  for i in range(N) :
    if A[i] > now :
      return -1
    if A[i] == 0 :
      now = 1
    else :
      now += 1

  ret = 0
  for i in range(1, N) :
    if A[i] == 0 :
      continue

    ret += 1
    if A[i] != A[i-1] + 1 :
      ret += A[i] - 1
  
  return ret

print(solve())

Submission status: Wrong Answer

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

def solve() :
  now = 0
  for i in range(N) :
    if A[i] > now :
      return -1
    if A[i] == 0 :
      now = 1
    else :
      now += 1

  ret = 0
  for i in range(1, N) :
    if A[i] == 0 :
      continue
    
    ret += 1
    if A[i] != A[i-1] + 1 :
      ret += A[i] * (A[i] - 1) // 2
  
  return ret

print(solve())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N): a.append(int(input()))
if a[0] != 0:
  print(-1)
  exit(0)
for i in range(N - 1):
  if a[i + 1] > a[i] and (a[i + 1] - a[i] > 1):
    print(-1)
    exit(0)
res = 0
s = 0
x = 1
for i in range(1, N):
  if a[i] == x:
    s += 1
  else:
    if x > 0: res += (s - 1) * x + 1
    if x > a[i]:
      res += a[i] - 1
    s = 1
    x = a[i]
  #print(i, res)
if x > 0: res += (s - 1) * x + 1
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N): a.append(int(input()))
if a[0] != 0:
  print(-1)
  exit(0)
for i in range(N - 1):
  if a[i + 1] > a[i] and (a[i + 1] - a[i] > 1):
    print(-1)
    exit(0)
res = 0
s = 0
x = 1
for i in range(1, N):
  if a[i] == x:
    s += 1
  else:
    if x > 0: res += (s - 1) * x + 1
    s = 1
    x = a[i]
  #print(i, res)
if x > 0: res += (s - 1) * x + 1
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N): a.append(int(input()))
if a[0] != 0:
  print(-1)
  exit(0)
for i in range(N - 1):
  if abs(a[i + 1] - a[i]) > 1:
    print(-1)
    exit(0)
res = 0
s = 0
x = 1
for i in range(1, N):
  if a[i] == x:
    s += 1
  else:
    if x > 0: res += (s - 1) * x + 1
    s = 1
    x = a[i]
  #print(i, res)
res += (s - 1) * x + 1
print(res)

Submission status: Wrong Answer

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

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

if a[0] == 0:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n, *a = map(int, open(0).read().split())
ans = 0
if a[0] != 0:
	print(-1)
	exit()
for x, y in zip(a, a[1:]):
	if x + 1 < y:
		print(-1)
		exit()
	if x >= y:
		ans += x
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
ans=0
bef=0
if a[0]!=0:
	print(-1)
	exit()
for x in a[::-1]:
	if bef==0:
		if x:
			ans+=1
			bef=x
		continue
	if x+1<bef:
		print(-1)
		exit()
	ans+=(x!=bef-1)+(bef>1)
	bef=x
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
ans=0
bef=0
if a[0]!=0:
	print(-1)
	exit()
for x in a[::-1]:
	if bef==0:
		ans+=1
		bef=x
		continue
	if x+1<bef:
		print(-1)
		exit()
	ans+=(x!=bef-1)+(bef>1)
	bef=x
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=[int(input()) for i in range(n)]
for i in range(n):
  if a[i]>i:
    print(-1)
    sys.exit()
ct=0
for i in range(n-1,0,-1):
  if a[i]-1==a[i-1]:
    ct+=1
  else:
    ct+=a[i]
print(ct)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
cur = -1
c = 0
for i in a:
  pre,cur = cur,i
  if cur == 0:
    continue
  elif cur <= pre + 1:
    c += 1
  else:
    print(-1)
    exit()
print(c)

Submission status: Wrong Answer

Solution code:
#Sequence Growing Easy

import sys
input = sys.stdin.readline

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

judge = 1
for i in range(N):
    if i != N-1:
        if A[i+1] <= A[i]+1 and A[i] <= i:
            pass
        else:
            judge = 0
    else:
        if A[i] <= i:
            pass
        else:
            judge = 0

if judge == 0:
    print(-1)
else:
    n = 1
    for i in range(N-1):
        if A[(N-2)-i] == 0:
            n = n
        elif A[(N-2)-i] < A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + 1
        elif A[(N-2)-i] == A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + A[(N-2)-i]
        elif A[(N-2)-i] > A[(N-1)-i] and A[(N-1)-i] != 0:
            n = n + A[(N-1)-i]
        else:
            n = n + 1
    print(int(n))

Submission status: Wrong Answer

Solution code:
#Sequence Growing Easy

import sys
input = sys.stdin.readline

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

judge = 1
for i in range(N):
    if i != N-1:
        if A[i+1] <= A[i]+1 and A[i] <= i:
            pass
        else:
            judge = 0
    else:
        if A[i] <= i:
            pass
        else:
            judge = 0

if judge == 0:
    print(-1)
else:
    n = 1
    for i in range(N-1):
        if A[(N-2)-i] == 0:
            n = n
        elif A[(N-2)-i] < A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + 1
        elif A[(N-2)-i] == A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + A[(N-2)-i]
        else:
            n = n + A[(N-1)-i]
    print(int(n))

Submission status: Wrong Answer

Solution code:
#Sequence Growing Easy

import sys
input = sys.stdin.readline

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

judge = 1
for i in range(N):
    if i != N-1:
        if A[i+1] <= A[i]+1 and A[i] <= i:
            pass
        else:
            judge = 0
    else:
        if A[i] <= i:
            pass
        else:
            judge = 0

if judge == 0:
    print(-1)
else:
    n = 1
    for i in range(N-1):
        if A[(N-2)-i] == 0:
            n = n
        elif A[(N-2)-i] < A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + 1
        elif A[(N-2)-i] == A[(N-1)-i] and A[(N-2)-i] != 0:
            n = n + A[(N-2)-i]
        else:
            n = n + 1
    print(int(n))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g

def main():
    n=inp()
    a=inplm(n)
    ans=0
    if a[0]!=0:
        print(-1)
        return
    for i in range(n-1):
        if a[i+1]>a[i]+1:
            print(-1)
            return
        if a[i+1]-a[i]<0 and a[i+1]!=0 and a[i+1]!=1:
            print(-1)
            return
        if a[i+1]==0:
            continue
        elif a[i+1]==a[i] and a[i]!=1:
            ans+=2
        else:
            ans+=1
        print(ans)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g

def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g

def main():
    n=inp()
    a=inplm(n)
    ans=0
    if a[0]!=0:
        print(-1)
        return
    for i in range(n-1):
        if a[i+1]>a[i]+1:
            print(-1)
            return
        if a[i+1]-a[i]<0 and a[i+1]!=0 and a[i+1]!=1:
            print(-1)
            return
        if a[i+1]==a[i] and a[i]!=1:
            ans+=2
        elif a[i+1]==0:
            continue
        else:
            ans+=1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [0] * N
for i in range(N):
    A[i] = int(stdin.readline().rstrip())

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [ int(input()) for _ in range(n) ]
dp = [-1]*n
if A[0] != 0:
  print(-1)
else:
  dp[0] = 0
  for i in range(n-1):
    if A[i+1] <= A[i]:
      dp[i+1] = dp[i] + A[i+1]
    else:
      dp[i+1] = dp[i] + A[i+1] - A[i]
  print(dp[n-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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()
answer = 0
dp = [0 for _ in range(N)]
for i in range(1, N):
    add = A[i]
    if A[i] > A[i-1]:
        add = A[i] - A[i-1]
        dp[i] = A[i-1]+1
    elif A[i] > dp[i-1]:
        add = 1
        dp[i] = dp[i-1]+1
    else:
        dp[i] = 0
    answer += add
print(answer)

Submission status: Wrong Answer

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

if A[0] != 0:
    print(-1)
    exit()
answer = 0
dp = [0 for _ in range(N)]
for i in range(1, N):
    add = A[i]
    if A[i] > A[i-1]:
        add = A[i] - A[i-1]
        dp[i] = A[i-1]+1
    elif A[i] > dp[i-1]:
        add = 1
        dp[i] = dp[i-1]+1
    else:
        dp[i] = min(1, A[i])
    answer += add
print(answer)

Submission status: Wrong Answer

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

if A[0] != 0:
    print(-1)
    exit()
answer = 0
dp = [[0] for _ in range(N)]
for i in range(1, N):
    add = A[i]
    
    for x in dp[i-1]:
        
        if 0 < A[i]-x < add:
            dp[i].append(x+1)
            add = A[i]-x
    dp[i].append(A[i])
    answer += add
print(answer)

Submission status: Wrong Answer

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

if A[0] != 0:
    print(-1)
    exit()
answer = 0
dp = [[0] for _ in range(N)]
for i in range(1, N):
    add = A[i]
    for x in dp[i-1]:
        dp[i].append(x+1)
        if 0 < A[i]-x+1 <= add:
            dp[i] = [0, x+1]
            add = A[i]-x+1
    
    answer += add
print(answer)

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = []
	for i in range(N):
		a = int(input())
		A.append(a)

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

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

tmp=0
for i in a:
    if tmp<i:
        if tmp+1!=i:
            print(-1)
            exit()
    tmp=i
ans=0
p=0
q=0
for i in a:
    if q+1==i:
        if p==0:
            p=i
        else:
            p+=1
    elif q==i:
        p+=i
    else:
        ans+=p
        p=0
    q=i
ans+=p
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

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

A.reverse()

ans = 0

for i in range(N):

    if i == 0:
        ans += A[i]

    else:

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

        else:
            ans += A[i] - (A[i-1]-1)

print (ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=[0]*(n+1)
for i in range(n):
    s=int(input())
    lists[i]=s
uselist=[]
index=0
behind=0
lists[n]=-1
while index<=n-1:
    if lists[index]<=lists[index+1]:
        index+=1
    else:
        uselist.append(lists[behind:index+1])
        behind=index+1
        index+=1
import math 
if uselist[0][0]!=0:
    print(-1)

else:
    ans=0
    for some in uselist:
        flag=True
        for i in range(len(some)-1):
            ans+=some[i]
            if some[i]+1<some[i+1]:
                flag=False
                break
        if flag:
            k=some[-1]
            ans+=k
            ans-=k*(k-1)//2
        elif not flag:
            print(-1)
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=[0]*(n+1)
for i in range(n):
    s=int(input())
    lists[i]=s
uselist=[]
index=0
behind=0
lists[n]=-1
while index<=n-1:
    if lists[index]<=lists[index+1]:
        index+=1
    else:
        uselist.append(lists[behind:index+1])
        behind=index+1
        index+=1
import math 
if uselist[0][0]>=1:
    print(-1)
else:
    ans=0
    for some in uselist:
        for i in range(len(some)):
            ans+=some[i]
        k=some[-1]
        ans-=k*(k-1)//2
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
l=[]
for i in range(N):
    l.append(int(input()))

def calc(list):
    num=0
    sum=0
    
    while len(list)>1:
        if list[-2]==list[-1]:
            break
        else:
            list.pop(-1)
            sum+=1
    
    list.pop(-1)#最後の一文字の分はsumに+1すれば安心
    if len(list)==0:
        return sum+1
    else:
        """
        l_max=max(list)
        for i in range(1,l_max+1)[::-1]:
            num+=list.count(i)
            sum+=num
        """
        for item in list:
            sum+=item
        return sum+1
    

temp=[]
ans=0
judge=True
num=N

if l[0]!=0:
    print(-1)
    exit()
    
while True:
    num-=1
    #01231でだめになってる
    if l[num]==1:
        temp=l[num:]
        ans+=calc(temp)
        del l[num:]
        temp.clear
    elif l[num]==0:
        l.pop(-1)
    elif (l[num]-l[num-1])!=0 and (l[num]-l[num-1])!=1:
        print(-1)
        exit()
    else:
        pass
    if num==0:
        break
    
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
l=[]
for i in range(N):
    l.append(int(input()))

def calc(list):
    num=0
    sum=0
    l.pop(-1)
    l_max=max(list)
    for i in range(1,l_max+1)[::-1]:
        num+=l.count(i)
        sum+=num
    return sum+1
    

temp=[]
ans=0
judge=True
num=N

while judge:
    num-=1
    #01231でだめになってる
    if (l[num]-l[num-1])!=0 and (l[num]-l[num-1])!=1:
        judge=False
    elif l[num]==1:
        temp=l[num:]
        ans+=calc(temp)
        del l[num:]
        temp.clear
    elif l[num]==0:
        l.pop(0)
    else:
        pass
    if num==0:
        break
    
if judge==False:
    print(-1)
else:
    print(ans)
#ほぞん

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ans = 0
pre = 0
for i in range(N):
  if A[i] > i:
    print(-1)
    exit()
  else:
    if A[i] > 0:
      if A[i] == pre + 1:
        ans += 1
      else:
        ans += A[i]
    pre = 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 = a[-1]
x = a[-1]
for i in range(n-1):
    if a[-i-2] >= x-1:
        ans += a[-i-2]-x+1
        x = a[-i-2]
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:
# AGC024C - Sequence Growing Easy
def main():
    N, *A = map(int, open(0))
    if A[0]:  # corner case
        print(-1)
    else:
        ans = sum(j if j <= i else j - i for i, j in zip(A, A[1:]))
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# AGC024C - Sequence Growing Easy
def main():
    N, *A = map(int, open(0))
    if A[0]:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = 0
p = 0
for i in range(1,N+1):
  if ls[i-1]+1<ls[i]:
    print(-1)
    break
  if ls[i-1]+1==ls[i]:
    if i==N:
      ans += (ls[i])
    p = ls[i]
    continue
  else:
    ans += p
    p = ls[i]
else:
  print(ans)

Submission status: Wrong Answer

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

ans = 0
p = 0
for i in range(1,N+1):
  if ls[i-1]+1<ls[i]:
    print(-1)
    break
  if ls[i-1]+1==ls[i]:
    if i==N:
      ans += (ls[i])
    p = ls[i]
    continue
  else:
    ans += p
    p = ls[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ls = []
for i in range(N):
  ls += [int(input())]

ans = 0
p = -1
for i in range(N):
  if i<ls[i]:
    print(-1)
    break
  if p+1==ls[i]:
    if i==N-1:
      ans += (p+1)
    p = ls[i]
    continue
  else:
    ans += p
    p = ls[i]

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
ans=0
chk=True
cur=0
for i in reversed(range(n)):
  if A[i]==cur:
    cur-=1
    continue
  else:
    if A[i]>i:
      chk=False
    else:
      ans+=A[i]
      cur=A[i]-1
print(ans if chk else -1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
def Solve(n,A):
    if n==1:
        print(-1 if A[0]!=0 else 0)
    else:
        ret=0
        for i in range(n):
            if i==0:
                if A[i]!=0:
                    return -1
            else:
                if A[i]==A[i-1]+1:
                    ret+=1
                elif A[i]<=A[i-1]:
                    ret+=A[i]
                else:
                    return -1
        return ret
print(Solve(N,A))

Submission status: Wrong Answer

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

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

if t != 0:
    ans = -1
print(ans)

Submission status: Wrong Answer

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

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

if t != 0:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
tab = [0]*N
for i,a in enumerate(A):
    dst = i-a
    if dst < 0 or dst >=N:
        print(-1)
        exit()
    tab[dst] = max(tab[dst], a)
print(sum(tab))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
tab = [0]*N
for i,a in enumerate(A):
    dst = i-a+1
    if dst <= 0 or dst >=N:
        print(-1)
        exit()
    tab[dst] = max(tab[dst], a)
print(sum(tab))

Submission status: Wrong Answer

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

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

    blocks=[[]]
    prev=0
    for a in A[1:]:
        if a<prev:
            if a > 1:
                return -1
            blocks.append([])
        if a>prev+1:
            return -1
        if a>0:
            blocks[-1].append(a)
        prev=a


    cnts=[]
    for block in blocks:
        i,n,prev=0,len(block),1
        cnts.append([])
        while i<n:
            cnt=0
            while i<n and block[i]==prev:
                i+=1
                cnt+=1
            cnts[-1].append(cnt)
            if i<n:
                prev=block[i]

    ans = 0
    for cnt in cnts:
        prev = 1
        for c in reversed(cnt):
            tmp = c+(prev-1)
            ans += tmp
            prev = tmp
    return ans
        
print(solve(A))

Submission status: Wrong Answer

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

ok = True
for i, a in enumerate(A):
    if a > i:
        ok = False
        break

if not ok:
    print(-1)
else:
    c = 0
    for i in range(N-1):
        if A[i+1] != A[i] + 1:
            c += A[i+1]
        else:
            c += 1
    print(c)

Submission status: Wrong Answer

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

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

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 reversed(range(N)):
    if i == N-1:  
        ans += A[i]
    else:
        if A[i+1] != 0 and A[i] > A[i+1]:
            print(-1)
            exit()
        elif A[i] == A[i+1]:
            ans += A[i]
        elif A[i] == A[i+1] - 1:
            continue
        elif A[i+1] == 0:
            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 reversed(range(N)):
    if i == N-1:  
        ans += A[i]
    else:
        if A[i] > A[i+1]:
            print(-1)
            exit()
        elif A[i] == A[i+1]:
            ans += A[i]
        elif A[i] == A[i+1] - 1:
            continue
        elif A[i+1] == 0:
            ans += A[i]


print(ans)