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:
#!python
# -*- coding: utf-8 -*-


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

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

    count = 0

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

        one_index = i - A[i] + 1

        if one_index <= 0:
            count = -1
            break

        for j in range(one_index, i + 1):
            X[j] = X[j - 1] + 1
            count += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

    count = 0

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

        one_index = i - A[i] + 1

        if one_index <= 0:
            count = -1
            break

        for j in range(one_index, i + 1):
            X[j] = X[j - 1] + 1
            count += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

count=0
be=0
if a[0]==0:
    for i in a[1:]:
        #print(i,count)
        if i<=a[i-1]+1:
            if i>be: count+=1
            else: count +=i
            be=i
        else:
            print('-1')
            break
    print(count)
else: print('-1')

Submission status: Wrong Answer

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

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

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

res += A[N-1]

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
ans = 0
flag = True
for i in range(n):
    A = int(input())
    a.append(A)
next = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        next = 0
        continue
    if next - a[i] == 1:
        next = a[i]
        continue
    if next - a[i] >= 2:
        flag = False
        break
    next = a[i]
    ans += a[i]
if a[0] != 0:
    flag = False
# if flag:
#     #print(ans)
# else:
#     #print(-1)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys,collections,random,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
d = collections.defaultdict(int)
for i in range(n):
    d[I()] = i
d[0] = n
t,maxinc = 0,0
for i in range(1,n+1):
    if d[i-1] < d[i]:
        t += 1
        maxinc = max(maxinc,t)
    else:
        t = 0
print(n-1-maxinc)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
#A = list(map(int, list(S)))

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

frag = []
start = 1
for i in range(2, N):
    if A[i]==1:
        end = i - 1
        #print(start,end,A[start:end+1])
        frag.append(A[start:end+1])
        start = i
#print(start,N-1,A[start:])
frag.append(A[start:])
#print(frag)

ans = 0
for f in frag:
    s = sum(f)
    if s==1:
        ans += 1
    else:
        ans += s - 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
ans = 0
flag = True
for i in range(n):
    A = int(input())
    a.append(A)
next = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        next = 0
        continue
    if next - a[i] == 1:
        next = a[i]
        continue
    if next - a[i] >= 2:
        flag = False
        break
    next = a[i]
    ans += a[i]
if a[0] != 0:
    flag = False
if flag:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*N
div = []
flg = False
for i in range(N):
	a[i] = int(input())
	if i != 0:
		if a[i] - a[i-1] > 1:
			flg = True
		if a[i-1] > a[i]:
			div.append(i)

if a[N-1] >= a[N-2]:
	div.append(N)

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

ans = 0
p = 0
for index in div:
	s = a[index-1]
	for i in range(index-1,p,-1):
		if a[i] == a[i-1]:
			s += a[i-1]
	ans += s
	p = index

print(ans)

Submission status: Wrong Answer

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


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

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

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

    count = 0

    for i in range(N - 1, 0, -1):
        if A[i] > A[i - 1] + 1:
            count = -1
            break

        if A[i] == 0:
            continue

        count += 1
        if A[i] > 1:
            count += A[i - 1] - (A[i] - 1)

    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


if la[0] != 0:
    print(-1)
else:
    count = 0
    for n1, n2 in zip(la[:n-1], la[1:]):
        count += (n2 - n1) if (n2 - n1) > 0 else 1
    print(count)

Submission status: Wrong Answer

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

for i, a in enumerate(A):
    line_n = i - a
    if line_n < 0:
        print(-1)
        break
    if line_n in line:
        line[line_n] = max(line[line_n], a)
    else:
        line[line_n] = a
else:
    print(sum(line.values()))

Submission status: Wrong Answer

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


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

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

    count = 0

    for i in range(N - 1, 0, -1):
        if A[i] > A[i - 1] + 1:
            count = -1
            break

        if A[i] == 0:
            continue

        count += 1
        if A[i] > 1:
            count += A[i - 1] - (A[i] - 1)

    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()

A = []
for _ in range(N):
  A.append(read())

if A[0] != 0 or not all(A[i-1] >= A[i] - 1 for i in range(1, N)):
  print(-1)
  exit()

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

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
ans=0
A=[]
for i in range(N):
    A.append(int(raw_input()))
Ar=list(reversed(A))
tmp=Ar[0]
for i in range(0, N-1):
    if (Ar[i] - Ar[i+1]) > 1:
        ans=-1
        break
    elif (Ar[i] - Ar[i+1]) != 1:
        if i+Ar[i] >= N:
            ans = -1
            break
        ans += tmp
        tmp =Ar[i+1]
if Ar[N-1]!=0:
    ans = -1
if Ar[N-1]==0 and Ar[N-2]==1:
    ans+=tmp

print ans

Submission status: Wrong Answer

Solution code:
import numpy as np

line = input()

N = int(line)
A = np.array([0]*N)

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np


def solve(n, aaa):
    if aaa[0] > 0:
        return -1
    if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])):
        return -1
    ans = 0

    while any(aaa):
        new = [0] * n
        for i, (a0, a1) in enumerate(zip(aaa, aaa[1:])):
            if a1 == 0:
                continue
            ans += 1
            if a1 - a0 < 1:
                new[i] = a1 - 1
        aaa = [0] + np.trim_zeros(new)
    return ans


n = int(input())
aaa = list(map(int, (input() for _ in range(n))))
print(solve(n, aaa))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
ans,flag = 0,True
for i in range(n-1):
	if a[i]+1==a[i+1]: ans+=1
	elif a[i]>=a[i+1]: ans+=a[i+1]
	else:
		flag = False
		break
if flag: print(ans)
else: print(-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = map(int, stdin.read().split(), repeat(10, n))
    if a[0]:
        print -1
        return
    s = 0
    for i in xrange(1, n):
        if a[i] > a[i-1]:
            s += a[i] - a[i-1]
        else:
            s += a[i]
    print s
main()

Submission status: Wrong Answer

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

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

dp = [0]*N

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

Submission status: Wrong Answer

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

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

dp = [0]*N

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

Submission status: Wrong Answer

Solution code:
import numpy as np

line = input()

N = int(line)
A = np.array([0]*N)

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

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

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
if a[0] != 0:
    print(-1)
    exit()
for i in range(n-1):
    if a[i+1] - a[i] > 1:
        print(-1)
        exit()
for _ in range(n):
    if set(a) == set([-1,0]) or set(a) == set([0]):
        break
    i = a.index(max(a))
    if i == 0:
        print(-1)
        exit()
    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()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#from numba import njit

n = int(input())
a = np.array([int(input()) for _ in range(n)])
ans = 0
for _ in range(n):
    if set(a) == set([-1,0]) or set(a) == set([0]):
        break
    i = a.argmax()
    if i == 0:
        print(-1)
        exit()
    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()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import *
n = int(input())
a = [int(input()) for _ in range(n)]
tmp = deepcopy(a)
ans = 0
for _ in range(n):
    if set(a) == set([0]):
        break
    i = a.index(max(a))
    if i == 0:
        print(-1)
        exit()
    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: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
for _ in range(n):
    if set(a) == set([-1,0]) or set(a) == set([0]):
        break
    i = a.index(max(a))
    if i == 0:
        print(-1)
        exit()
    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()
print(ans)

Submission status: Time Limit Exceeded

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

b=[0]*n
#print(a)
for ii in range(1,n):
    i=n-ii
    if a[i]==b[i]:
        continue
    elif a[i]<b[i] or a[i]>i:
        print(-1)
        exit()
    else:
        for k in range(a[i]+1):
            b[i-k]=a[i]-k
        cnt+=a[i]

    #print(b)

print(cnt)

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

"""

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=""
res=0
for i in range(n):
  a+=input()
if int(a[0])!=0:
  print(-1)
  exit()
for  i in range(n-1):
  a2=int(a[i+1])
  a1=int(a[i])
  if a2-a1>1:
    print("-1")
    exit()
  if a2<=a1:
    res+=a1
res+=int(a[n-1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = [0]*n
    f = True
    ans = 0
    for i in reversed(range(n)):
        if i < a[i] or a[i] < b[i]:
            f = False
            break
        if b[i] < a[i]:
            for j in range(i-a[i], i):
                ans += 1
                b[j+1] = b[j]+1
    if f:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())




def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact





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


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

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

count = 0
x = [0]*N

for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1


print(count)

Submission status: Time Limit Exceeded

Solution code:


from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())




def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def serch(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


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


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

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

count = 0
x = [0]*N

for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1


print(count)

Submission status: Time Limit Exceeded

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(len(A)-1, -1, -1):
    if A[i] == 0:
        continue
    add = 0
    j = i - 1
    k = A[i] - 1
    while j >= 0:
        if A[j] == k or dp[j] == k:
            add = i - j
            break
        elif A[j] > k:
            dp[j] = k
            j -= 1
            k -= 1
        else:
            print(-1)
            exit()
    answer += add
print(answer)

Submission status: Time Limit Exceeded

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(len(A)-1, -1, -1):
    if A[i] == 0:
        continue
    add = A[i] - dp[i]
    j = i - 1
    k = A[i] - 1
    while j >= 0:
        if A[j] == k or dp[j] == k:
            add = i - j
            break
        elif A[j] > k:
            dp[j] = k
            j -= 1
            k -= 1
        else:
            print(-1)
            exit()
    answer += add
print(answer)

Submission status: Time Limit Exceeded

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(len(A)-1, -1, -1):
    if A[i] == 0:
        continue
    add = A[i] - dp[i]
    j = i - 1
    k = A[i] - 1
    while j >= 0:
        if A[j] == k or dp[j] == k:
            add = i - j
            break
        elif A[j] > k:
            dp[j] = k
            if j > 0:
                j -= 1
                k -= 1
            else:
                
                print(-1)
                exit()
        else:
            
            print(-1)
            exit()
    answer += add
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Value:
    def __init__(self, val, f):
        self.val = val
        self.key = f(val)

    def __lt__(self, other):
        return self.key < other.key

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, f=lambda x: x):
        for i in range(len(arr)):
            arr[i] = Value(arr[i], f)
        self.func = f
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq).val

    def push(self, a):
        heapq.heappush(self.hq, Value(a, self.func))

    def top(self):
        return self.hq[0].val


n = int(input())
a = [int(input()) for _ in range(n)]
if a[0] > 0:
    print(-1)
    exit(0)
hq = Heapq([], f=lambda x: (-a[x], x))
for i, x in enumerate(a):
    if x > 0:
        hq.push(i)
ans = 0
while hq.hq:
    i = hq.pop()
    if a[i] - 1 == a[i - 1]:
        ans += 1
        a[i] = (a[i + 1] - 1 if i != n - 1 else 0)
        if a[i] > 0:
            hq.push(i)
    else:
        print(-1)
        exit(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
if a[0] != 0:
    print("-1")
else:
    x = [0] * len(a)
    b = 9999
    c = 0
    for i in range(len(a) - 1, 0, -1):
        if a[i] == x[i]:
            continue
        if i - a[i] < 0:
            break 
        for j in range(1, a[i]+1):
            x[i - a[i] + j] = j
            c += 1
    if a == x:
        print(c)
    else:
        print("-1")

Submission status: Time Limit Exceeded

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

X = [0]*(n+1)
count = 0
if A[1] != 0:
    print(-1)
else:
    for i in range(n,0,-1):
        if A[i] > X[i]:
            for j in range(A[i]):
                X[i-j] = A[i] - j
            count += A[i]
        elif A[i] < X[i]:
            print(-1)
            break
    else:
        print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

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

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

result = 0
last = n
b = [0 for i in range(n)]
while 1:
    for i in range(last):
        j = last - i - 1
        if a[j] != b[j]:
            start = j
            last = j
            max_diff = a[j]
            break
    if j == 0:
        print(result)
        exit()
    for i in range(max_diff):
        b[start - i] = max_diff - i
    result += max_diff

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

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

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

result = 0
last = n
b = [0 for i in range(n)]
while a != b:
    for i in range(last):
        j = last - i - 1
        if a[j] != b[j]:
            start = j
            last = j
            max_diff = a[j]
            break
    for i in range(max_diff):
        b[start - i] = max_diff - i
    result += max_diff

print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

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

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

result = 0
b = [0 for i in range(n)]
while a != b:
    max_diff = 0
    for i in range(n):
        j = n - i - 1
        if a[j] != b[j]:
            if a[j] > max_diff:
                start = j
                max_diff = a[j]
    for i in range(max_diff):
        b[start - i] = max_diff - i
    result += max_diff

print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

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

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

result = 0
b = [0 for i in range(n)]
while a != b:
    max_diff = 0
    for i in range(n):
        if a[i] != b[i]:
            if a[i] > max_diff:
                start = i
                max_diff = a[i]
    for i in range(max_diff):
        if b[start - i] != a[start - i]:
            b[start - i] = max_diff - i
    result += max_diff

print(result)

Submission status: Time Limit Exceeded

Solution code:
def solve0(N, A):
    p = -1
    for i, x in enumerate(A):
        if x > p + 1:
            return -1
        p = x
    r = 0
    p = set([0])
    for i in range(N - 1, -1, -1):
        c = 0
        q = set(n - 1 for n in p if n - 1 >= 0)
        q.add(A[i])
        r += len(q)
        if 0 in q:
            r -= 1
        print("*", A[i], c, r, p, q)
        p = q
    return r

def solve(N, A):
    p = -1
    for x in A:
        if x > p + 1:
            return -1
        p = x
    r = 0
    p = [0]
    for i in range(N - 1, -1, -1):
        q = [n - 1 for n in p if n >= 2]
        a = A[i]
        if a > 0 and (not q or q[-1] != a):
            q.append(a)
        r += len(q)
        # print("*", A[i], c, r, p, q)
        p = q
    return r

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

print(solve(N, A))

Submission status: Time Limit Exceeded

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

def solve(a):
    peaks = find_peaks(a)
    if all(check_peak(a, p) for p in peaks):
        return sum(a[p] for p in peaks)
    else:
        return -1

def check_peak(a, peak):
    if a[peak] > peak:
        return False
    
    base = peak - a[peak]
    for i in range(a[peak]):
        if a[base + i] < i:
            return False
    
    return True

def find_peaks(a):
    peaks = []

    for i in range(len(a) - 1):
        if a[i] != 0 and a[i + 1] <= a[i]:
            peaks.append(i)
    
    if a[len(a) - 1] != 0:
        peaks.append(len(a) - 1)
    
    return peaks

main()

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A):
    p = -1
    for i, x in enumerate(A):
        if x > p + 1:
            return -1
        p = x
    r = 0
    p = set([0])
    for i in range(N - 1, -1, -1):
        c = 0
        q = set(n - 1 for n in p if n - 1 >= 0)
        q.add(A[i])
        r += len(q)
        if 0 in q:
            r -= 1
        # print("*", A[i], c, r, p, q)
        p = q
    return r

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

print(solve(N, A))

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A):
    p = -1
    for i, x in enumerate(A):
        if x > p + 1:
            return -1
        p = x
    r = 0
    p = set([0])
    for i in range(N - 1, -1, -1):
        c = 0
        q = set([n - 1 for n in p if n - 1 >= 0] + [A[i]])
        """
        if A[i] == 0:
            c = 0
        elif i == N - 1:
            c = 1
        elif A[i + 1] == 1 or A[i + 1] == 0:
            c = 1
        elif A[i] == A[i + 1] - 1:
            c = 1
        else:
            c = 2
        """
        r += len(list(n for n in q if n >= 1))
        # print("*", A[i], c, r, p, q)
        p = q
    return r

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

print(solve(N, A))

Submission status: Time Limit Exceeded

Solution code:
def solve(n, aaa):
    if aaa[0] > 0:
        return -1
    if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])):
        return -1
    ans = 0
    aaa.reverse()

    while any(aaa):
        while aaa[-1] == 0:
            aaa.pop()
        aaa.reverse()
        while aaa[-1] == 0:
            aaa.pop()
        aaa.reverse()

        new = [0] * (len(aaa) - 1)
        a1 = aaa[0]
        ap = 0
        for i, a0 in enumerate(aaa[1:]):
            if a1 == 0:
                a1 = a0
                continue
            ans += 1
            if a1 - a0 < 1:
                new[i] = ap = max(a1 - 1, ap)
            else:
                new[i] = ap
            a1 = a0
            if ap:
                ap -= 1
        if a1:
            ans += 1
        aaa = new
    return ans


n = int(input())
aaa = list(map(int, (input() for _ in range(n))))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A):
    xs = []
    p = []
    for i, x in enumerate(A):
        e = [0] + [n + 1 for n in p if n + 1 <= x]
        if not x in e:
            return -1
        p = e
        xs.append(e)
    # print(xs)
    r = 0
    for i in range(N - 1, -1, -1):
        c = 0
        if A[i] == 0:
            c = 0
        elif i == N - 1:
            c = 1
        elif A[i + 1] == 1 or A[i + 1] == 0:
            c = 1
        elif A[i] == A[i + 1] - 1:
            c = 1
        else:
            c = 2
        r += c
        # print("*", A[i], c, r)
    return r

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

print(solve(N, A))

Submission status: Time Limit Exceeded

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

flag = True
for i in range(n - 1):
    if a[i + 1] - a[i] >= 2:
        flag = False
if a[0] != 0:
    flag = False

count = 0
start = 0
if flag == True:
    while a != [0] * n:
        for i in range(start, n - 1):
            if a[i] + 1 == a[i + 1]:
                start = i
                break
        for j in range(start, n - 1):
            if a[j] + 1 != a[j + 1]:
                end = j
                break
            if j == n - 2:
                end = n - 1
        for k in range(end, start - 1, -1):
            if end != n - 1:
                a[k] = max(0, a[k + 1] - 1)
            else:
                a[k] = 0
        count = count + end - start
if flag == False:
    print(-1)
else:
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(n, aaa):
    if aaa[0] > 0:
        return -1
    if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])):
        return -1
    ans = 0
    aaa.reverse()

    while any(aaa):
        new = [0] * (len(aaa) - 1)
        a1 = aaa[0]
        ap = 0
        for i, a0 in enumerate(aaa[1:]):
            if a1 == 0:
                a1 = a0
                continue
            ans += 1
            if a1 - a0 < 1:
                new[i] = ap = max(a1 - 1, ap)
            else:
                new[i] = ap
            a1 = a0
            if ap:
                ap -= 1
        aaa = np.trim_zeros(new)
        if a1:
            ans += 1
    return ans


n = int(input())
aaa = list(map(int, (input() for _ in range(n))))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

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

B = [0]*N
possible = True
tot = 0
for i in range(N):
    if A[-(i+1)] > N-i-1:
        possible = False
        break
    elif B[-(i+1)] > A[-(i+1)]:
        possible = False
        break
    elif B[-(i+1)] == A[-(i+1)]:
        continue
    else:
        if i == 0:
            B[-(i+1+A[-(i+1)]):] = range(A[-(i+1)]+1)
            tot += A[-(i+1)]
        else:
            B[-(i+1+A[-(i+1)]):-i] = range(A[-(i+1)]+1)
            tot += A[-(i+1)]
if not possible:
    print(-1)
else:
    print(tot)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(n, aaa):
    if aaa[0] > 0:
        return -1
    if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])):
        return -1
    ans = 0
    aaa.reverse()

    while any(aaa):
        new = [0] * (len(aaa) - 1)
        for i, (a1, a0) in enumerate(zip(aaa, aaa[1:])):
            if a1 == 0:
                continue
            ans += 1
            if a1 - a0 < 1:
                ap = a1
            else:
                ap = 0
            new[i] = max(ap - 1, new[i - 1] - 1, 0)
        aaa = np.trim_zeros(new) + [0]
    return ans


n = int(input())
aaa = list(map(int, (input() for _ in range(n))))
print(solve(n, aaa))