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: Runtime Error

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

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>

#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;


int main() {
    int n;
    cin >> n;
    vl a(n);
    rep(i,n)cin >> a[i];
    if(a[0] != 0){
        cout<<-1<<endl;
        return 0;
    }
    ll ans = 0;

    srep(i,1,n){
        if(a[i-1]==0 || a[i]<=1){
            //show("s1");
            ans+=a[i];
        }
        else if(a[i] <=a[i-1]){
            //show("s2");
            ans+=1;
        }else{
            //show("s3");
            ans+=max(1LL,a[i]-a[i-1]);
        }
        // a[i]=max(1LL,a[i]-a[i-1]);
        // if(a[i-1] != 0 && a[i]>=a[i-1])ans-=1;
    }
    cout<<ans<<endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[int(input()) for i in range(n)]
if l[0]!=0:
    print(-1)
    quit()
l.reverse()
ans=0
i=0
while i<n-2:
    if l[i]>n-i-1:
        print(-1)
        quit()
    if l[i+1]+1==l[i]:
        ans+=l[i]
        while l[i+1]+1==l[i]:
            i+=1
    elif l[i+1]+1<l[i]:
        print(-1)
        quit()
    else:
        ans+=l[i]
        i+=1
print(ans)

Submission status: Runtime Error

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


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


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: Runtime Error

Solution code:

import numpy as np
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())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


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: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
def func(lis):
    #print(lis)
    count=0
    while len(lis)>1 and lis[-1]!=lis[-2]:
        lis.pop(-1)
        count+=1
    
    loc=0
    l_count=0
    last=len(temp)-1
    count+=temp[0]*(temp[0]-1)//2+(temp[0]-1)*last
    pre=0
    for i in range(len(lis)-1):
        if lis[i]!=pre:
            loc+=i
            l_count+=1
            pre=lis[i]
    
    count+=l_count*last-loc
    
    return count+1

N=int(input())

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

temp=[]
ans=0
for _ in range(N-1):
    A=int(input())
    if A-pre>1:
        print(-1)
        exit()
    if A-pre<0:
        ans+=func(temp)
        temp=[]
        #print(ans)
    if A!=0:
        temp.append(A)
    pre=A
ans+=func(temp)

print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pos;
int main(){
  long N;cin>>N;
  vector<long> A(N);for(int i=0;i<N;i++)cin>>A[i];
  
  long ans=0;
  
  if(A[N-1]<N)ans+=A[N-1];
  else {cout<<-1;return 0;}
  for(int i=N-2;i>=0;i--){
    //あり得るのは, 一個後に比べて
    //  1だけ小さい (この時自然に作れる)
    //  2以上小さい ありえない()
    //  同じかそれ以上 再度コストを図る
    if(A[i]<A[i+1]-1){cout<<-1;return 0;}
    else if(A[i]>=A[i+1]){
      if(A[i]>i){cout<<-1;return 0;}
      ans+=A[i];
    }
    else{
      
    } 
  }
  cout<<ans;

}

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
if any(a - b > 1for a, b in zip(A, [-1]+A)): print(-1)
else:
    ans = 0
    for a, nxt in zip(A, A[1:]+[0]):
        if a >= nxt:
            ans += a
print(ans)

Submission status: Runtime Error

Solution code:
def makelist2(n, m):
    return [[0 for k in range(m)] for i in range(n)]


N = int(input())
A = []
append = A.append
for i in range(1,N+1):
    a = int(input())
    if a >=i:
        print(-1)
        exit()
    elif A[i-1] > a:
        print(-1)
        exit()
    append(a)

Submission status: Runtime Error

Solution code:
N = int(input())
l =[]
#deal with error
for i in range(N):
    l.append(int(input()))
    if i == 0 and l[i]!=0:
        print(-1)
        break
    if i>=1:
        if l[i]-l[i-1]>1 :
            print(-1)
            break

counter=0#answerになる。
counter_n=l[0]#listの中の重複を数える。
l = l[::-1]
for i in range(N-1):
    if l[i]<l[i+1]:
        counter+=counter_n
        counter_n=0#初期化
    elif l[i]==l[i+1]:
        if counter_n == 0:
            counter_n = 2*l[i]
        else:
            counter_n += l[i]
        counter_n += l[i]
    elif l[i] == l[i+1]+1:
        counter += 1
counter += counter_n
print(counter)

Submission status: Runtime Error

Solution code:
N = int(input())
ans = 0
bool1 = False

a0 = int(input())

for i in range(N-1):
    a1 = int(input())
    if i == 0 and a0 != 0:
        bool1 = True
        break
    if a1 - a0 > 1:
        bool1 = True
        break
    elif a1 - a0 == 1:
        a0 = a1
        continue
    else:
        ans += a0
        a0 = a1
       
if bool1 == True:
    print(-1)
else:
    print(ans + a1)

Submission status: Runtime Error

Solution code:
N = input()
A = []
for i in xrange(N):
	A.append(input())
ans = 0
start = 0
for i in xrange(N):
%	if A[i] > i - start:
	if A[i] > A[i-1] + 1:
		ans = -1
		break
	if i == 0:
		continue
	if A[i] == A[i - 1] + 1:
		ans += 1
		continue
	if A[i] == 0:
		start = i
		continue
	ans += A[i]
print ans

Submission status: Runtime Error

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

p = 1
n = 0
i = 1
if L[0] != 0:
    print(-1)
else:
    while True:
        if L[i] < p:
            p = 1
        L[i] -= p

        n += 1

        if L[i] == 0:
            i += 1
            p += 1
            if i == N: break
            if L[i] == 0:
                p = 1
                i += 1
            if i == N: break
            while L[i] == 0:
                i += 1
                if i == N: break

        if i==N: break

    print(n)

Submission status: Runtime Error

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
k = 0
for i in range(1,n+1):
    if p[i-1] - p[i]  < -1:
        print(-1)
        break
    elif p[i-1] - p[i]  == -1:
        k += 1
    elif p[i-1] - p[i]  == 0:
        k += p[i]

print(k)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lis = []
for i in range(n):lis.append(int(input()))
if lis[0] != 0:
    print("-1")
    exit()
cou = 0
print(lis,cou)
for k in range(n-1):
    if lis[n-(k+1)] > lis[n-(k+2)]:
        a =  math.ceil(lis[n-(k+1)] / (lis[n-(k+2)]+1))
        cou += a
        lis[n-(k+1)] = 0
        lis[n-(k+2)] = min(lis[n-(k+1)]-1,lis[n-(k+2)],math.ceil(lis[n-(k+1)]/a)-1)
    else:
        cou += lis[n-(k+1)]
        lis[n-(k+2)] -= lis[n-(k+1)]-1
        lis[n-(k+1)] = 0
    print(lis,cou)
print(cou)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lis = []
for i in range(n):lis.append(int(input()))
if lis[0] != 0:
    print("-1")
    exit()
cou = 0
print(lis,cou)
for k in range(n-1):
    if lis[n-(k+1)] > lis[n-(k+2)]:
        a =  math.ceil(lis[n-(k+1)] / (lis[n-(k+2)]+1))
        cou += a
        lis[n-(k+1)] = 0
        lis[n-(k+2)] = min(lis[n-(k+1)]-1,lis[n-(k+2)],math.ceil(lis[n-(k+1)]/a))
    else:
        cou += lis[n-(k+1)]
        lis[n-(k+2)] -= lis[n-(k+1)]-1
        lis[n-(k+1)] = 0
    print(lis,cou)
print(cou)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lis = []
for i in range(n):lis.append(int(input()))
if lis[0] != 0:
    print("-1")
    exit()
cou = 0
print(lis,cou)
for k in range(n-1):
    if lis[n-(k+1)] > lis[n-(k+2)]:
        cou += math.ceil(lis[n-(k+1)] / (lis[n-(k+2)]+1))
        lis[n-(k+1)] = 0
        lis[n-(k+2)] = min(lis[n-(k+1)]-1,lis[n-(k+2)])
    else:
        cou += lis[n-(k+1)]
        lis[n-(k+2)] -= lis[n-(k+1)]-1
        lis[n-(k+1)] = 0
    print(lis,cou)
print(cou)

Submission status: Runtime Error

Solution code:
line = input()

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

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

    
def IsNotPossible(A):
    for i in range(N): 
        ai = A[i]

        if ai > i:
            return 1

        for j in range(ai):
            if A[i-1-j] < ai-1-j:
                return 1

    return 0

if IsNotPossible(A):
    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: Runtime Error

Solution code:
import math
n = int(input())
lis = []
for i in range(n):lis.append(int(input()))
if lis[0] != 0:
    print("-1")
    exit()
cou = 0
print(lis,cou)
for k in range(n-1):
    if lis[n-(k+1)] > lis[n-(k+2)]:
        cou += math.ceil(lis[n-(k+1)] / (lis[n-(k+2)]+1))
        lis[n-(k+1)] = 0
    else:
        cou += lis[n-(k+1)]
        lis[n-(k+2)] -= lis[n-(k+1)]-1
        lis[n-(k+1)] = 0
    print(lis,cou)
print(cou)

Submission status: Runtime Error

Solution code:
N = int(input())

start = int(input())
flag = 0
if start != 0:
flag = 1
t = 0

for i in range(N-1):
 k = int(input())
 if k == start:
  t += start
 elif k == start + 1:
  t += 1
  start = k
 elif k == 0:
  start = 0
 elif k > start + 1:
  t = -1
  break
 else:
  t += k
  start = k

if flag ==1:
 t = -1
print(t)

Submission status: Runtime Error

Solution code:
#include <iostream>

using namespace std;
int line[200001];
int linep_r[200001];

int main(){
	int N;
	long long A[200001];
	cin >> N;
	for (int i=0; i<N; i++) {
		cin >> A[i];
	}
	for (int i=0; i<N; i++) {
		long long line_n = i - A[i];
		if (line_n < 0) {
			cout << -1 << endl;
			return 0;
		}
		line[line_n] = line[line_n] > A[i] ? line[line_n] : A[i];
	}

	long long ans = 0;

	int linep_max = 0;
	for (int i=0; i<200001; i++) {
		linep_max = linep_max > line[i]+i ? linep_max : line[i]+i;
		linep_r[i] = linep_max;
	}
	for (int i=1; i<N; i++) {
		if (i <= linep_r[i-A[i]-1]) {
			cout << -1 << endl;
			return 0;
		}
	}

	for (int i=0; i<200001; i++) {
		ans += line[i];
	}
	cout << ans << endl;



	return 0;
}

Submission status: Runtime Error

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):
        X[i] = X[i + 1] - 1
        if A[i] == X[i]:
            continue

        count += A[i]
        X[i] = A[i]

    print(count)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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: Runtime Error

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


def solve(tc):
    n = int(stdin.readline().strip())
    li = list()
    for i in range(n):
        li.append(int(stdin.readline().strip()))

    if li[0]>0:
        print(-1)
        return

    res = 0
    p = li[1]
    for i in range(2,n):
        if li[i]!=p+1:
            res += p
        p = li[i]
    res += p
    print(res)


tc = 1
solve(tc)

Submission status: Runtime Error

Solution code:
N = int(input())
ans = -1
bef = -1
for i in range(N):
    now = int(data[input()])
    if now - bef > 1:
        ans = -1
        break
    elif now - bef == 1:
        ans += 1
        bef = now
    else:
        ans += now
        bef = now

print(str(ans))