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: Accepted

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

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

ans = 0
for a,b in zip(A,A[1:]):
    if a+1 < b:
        print(-1)
        exit()
    if a+1 == b:
        ans += 1
    else:
        ans += b
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(n-1):
  a=int(input())
  if a>b+1:
    print(-1)
    exit()
  else:
    if a==b+1:
      c+=1
    else:
      c+=a  
  b=a
print(c)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    ans = -1
    prev = -1

    for x in a:
        if prev >= x:
            ans += x
            prev = x
        elif prev + 1 == x:
            ans += 1
            prev = x
        else:
            return print(-1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [-1]
ans = 0
for i in range(N):
    A.append(int(input()))
    if A[i+1] == 0:
        continue
    elif A[i+1] == A[i] + 1:
        ans += 1
    elif A[i+1] <= A[i]:
        ans += A[i+1]
    else:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
As = [int(input()) for i in range(n)]
dp  = [0] * n #どこまで伸ばせたか
mx = 0
prev = 0
for i,a in enumerate(As):
    if a == 0:continue
    # prev + 1より大きくなることはありえない
    if prev + 1 < a:
        print(-1)
        exit()
    if i - a < mx: #遡ってしまったら
        print(-1)
        exit()
    else:
        dp[i-a] = a
        mx = i-a
    prev = a
print(sum(dp))

Submission status: Accepted

Solution code:
import sys
N = int(input())
pre_a = int(input())
if pre_a != 0:
    print(-1)
    sys.exit()
ans = 0
for i in range(N-1):
    ai = int(input())
    if ai - pre_a < 1:
        ans += ai
    elif ai - pre_a == 1:
        ans += 1
    else:
        ans = -1
        break
    pre_a = ai

print(ans)

Submission status: Accepted

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

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

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


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

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

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

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

    return arr


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


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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

    divisors.sort()
    return divisors


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

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

Submission status: Accepted

Solution code:
#editorial https://ami-atcoder.hatenablog.com/entry/20191018/1571386871
n=int(input())
pre=int(input())
if pre!=0:print(-1);exit()
ans=0
for i in range(n-1):
    x=int(input())
    if x==pre+1:ans+=1
    elif pre<x:print(-1);exit()
    else:ans+=x
    pre=x
print(ans)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0))
if a[0] or any(c - b > 1 for b, c in zip(a, a[1:])):exit(print(-1))
b = ans = 0
for c in a[1:]:
  ans += b * (c - b != 1)
  b = c
print(ans + b)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a0=int(input())
if a0!=0:
    print(-1)
    exit()
ab=0
ans=0
for i in range(n-1):
    a=int(input())
    if a==ab+1:
        ans+=1
    elif a>ab+1:
        print(-1)
        exit()
    else:
        ans+=a
    ab=a
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(int(input()) for _ in range(n))

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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = list(in_all())

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = ILs(N)

ans = 0
req = 0

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

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
if a[0]!=0:
  print(-1)
  exit()
a.reverse()
pre=a[0]
tmp=pre
ans=0
for ai in a[1:]:
  if ai>=pre:
    ans+=tmp
    pre=ai
    tmp=ai
  elif ai+1==pre:
    pre=ai
  else:
    print(-1)
    exit()
ans+=tmp
print(ans)

Submission status: Accepted

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

for i in range(n-1):
    if a[i+1] - a[i] >= 2:
        print(-1)
        sys.exit()
        
if a[0] != 0:
    print(-1)
    sys.exit()
    
a.append(1145141919810)
se = []
pl = [a[0]]
for i in range(n):
    if a[i+1] - a[i] == 1 or a[i+1] - a[i] == 0:
        pl.append(a[i+1])
    else:
        se.append(pl)
        pl = [a[i+1]]
        
from collections import Counter
ans = 0
for l in se:
    b = Counter(l)
    ans += max(l)
    for i in b:
        ans += max(0,b[i]-1) * i
        
print(ans)

Submission status: Accepted

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

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

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

print(cnt)

Submission status: Accepted

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

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

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

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
a=[]
s=int(input())
if s!=0:
  print(-1)
  sys.exit()
a.append(s)
ans=0
prev=0
for i in range(n-1):
  x=int(input())
  if x-prev>1:
    print(-1)
    sys.exit()
  if x-prev==1:
    ans+=1
  else:
    ans+=x
  prev=x
print(ans)

Submission status: Accepted

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

if A[0] != 0:
    print(-1)
elif sum(A) == 0:
    print(0)
else:
    nonzero = []
    for i in range(1,N):
        if A[i] - A[i-1] > 1:
            print(-1)
            break
        if A[i] != 0:
            nonzero.append(A[i])
    else:
        ans = nonzero[0]-1
        for i in range(1,len(nonzero)):
            if nonzero[i-1] + 1 != nonzero[i]:
                ans += nonzero[i]-1
        print(ans+len(nonzero))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,read().split()))

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

if(n==1):
    print(0)
    exit()

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

res = 0
i = n-1
while i>=0:
    j = i
    while j-1>=0 and al[j]==al[j-1]+1:
        j -= 1
    res += al[i]
    if al[j]>j:
        print(-1)
        exit()
    if j-1>=0 and al[j-1]<al[j]:
        print(-1)
        exit()
    i = j-1
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

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

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


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


print(solve())

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    a = int(input())
    if a != 0:
        print(-1)
        return
    ans = 0
    flag = False
    for _ in range(N-1):
        tmp = int(input())
        if tmp == a + 1:
            ans += tmp
            ans -= a
        elif tmp < a + 1:
            ans += tmp
        else:
            print(-1)
            return
        a = tmp
    print(ans)    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + [int(input()) for i in range(N)]
if A[1] != 0:
  print(-1)
  quit()

ans = 0
for i, a in enumerate(A[1:], 1):
  pre_a = A[i-1]
  if a - pre_a >= 2:
    print(-1)
    quit()
  elif a > pre_a:
    ans += 1
  else:
    ans += a

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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]-A[i-1] >= 2:
        print(-1)
        exit()
    elif A[i]-A[i-1] == 1:
        ans += 1
    else:
        ans += A[i]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input())for i in range(n)]
x,y=-1,-1
for i in a:
 if i-x>1:print(-1);exit()
 elif i==x+1:y+=1
 else:y+=i
 x=i
print(y)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
prev = -1
res = -1
a = [int(input()) for _ in range(n)]
for i in a:

    if i - prev > 1:
        print(-1)
        exit()
    elif i == prev + 1:
        res += 1
    else:
        res += i
    prev = i

print(res)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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:
            if a[i] >= a[i-1] + 2:
                ans = -1
                break
            ans += a[i-1]

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

ans += a[n-1]

print(ans)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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

    if A[0] != 0:
        print(-1)
        return
    answer = 0
    flag = 0
    for i in range(N - 1):
        if A[i + 1] - A[i] > 1:
            print(-1)
            return
        elif A[i + 1] == A[i]:
            answer += A[i]
        elif A[i + 1] == A[i] + 1:
            flag = A[i + 1]
        else:
            answer += flag
            flag = A[i + 1]
    answer += flag
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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

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

    ans = 0
    i = N - 1
    while i > 0:
        M = A[i]
        ans += M
        while A[i] > A[i - 1] and i - 1 >= 0:
            i -= 1
        i -= 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans=0
for i in range(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: Accepted

Solution code:
n,r=int(input()),-1
a = [int(input()) for _i in range(n)]+[-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: Accepted

Solution code:
n = int(input())
a = [int(input()) for _i in range(n)] + [-1]

result = -1
for i in range(n):
    if a[i-1] >= a[i]:
        result += a[i]
    elif a[i-1] + 1 == a[i]:
        result += 1
    else:
        result = -1
        break
print(result)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _i in range(n)] + [-1]

result = -1
for i in range(n):
    if a[i-1] == a[i]:
        result += a[i]
    elif a[i-1] + 1 == a[i]:
        result += 1
    elif a[i-1] > a[i]:
        result += a[i]
    else:
        result = -1
        break
print(result)

Submission status: Accepted

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

cnt = 0
tmp = 0
for i in range(n):
    if a[i] > tmp:
        tmp = a[i]
        cnt += tmp


    elif a[i] < tmp:
        print(-1)
        exit()

    tmp -= 1

print(cnt)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans+=last
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

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

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



n = int(input())
a=[]
for i in range(n):
    a.append(int(input()))
    
#
if(a[0]!=0):
    print(-1)
    exit()
#
now = 0
ans = 0
for i in range(1,n):
    if(a[i]<=a[i-1]):
        ans+=max(0,a[i]-1)
    if(a[i]>=1):
        ans+=1
    if(a[i]>a[i-1]+1):
        print(-1)
        exit()

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#AGC024-C Sequence Growing Easy
"""
問題：
lst1とlst2がある。
lst1の値が与えられ、lst2の値は最初全て0である。
lst2[i+1] = lst2[i]+1
を繰り返し、lst1と等しくできる場合その最小手数を出力せよ。

考察：
足し合わせる、ではなく、置き換える、なので、
必ずlst2[i+1] <= lst2[i] + 1となる。
左から最大に足し合わせた場合、
0 1 2 3 4...としかならない。
他に
0 0 1 0 0
0 0 1 2 0
0 0 1 2 3
0 1 1 2 3
0 1 2 2 3
0 1 2 3 3 (3+3で6手)
のような遷移も可能
0 0 0 1 0
0 0 0 1 2
0 1 0 1 2
0 1 2 1 2
0 1 2 3 2 (3+2で5手)
解法：
左からリストを見ていった時に、
必ずlst1[i+1] <= lst1[i] + 1となっていることを確認しながら、
正常な遷移でない部分の値を足し合わせることによって答えが求まる
正常でない遷移：↑のシュミレーションの3+3とか3+2の部分
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
for i in range(n):
    lst1.append(int(readline()))
if lst1[0] != 0:
    print(-1)
    exit()
ans = 0
for i in range(n-1):
    if lst1[i]+1 == lst1[i+1]:
        continue
    if lst1[i]+1 < lst1[i+1]:
        print(-1)
        exit()
    if lst1[i] >= lst1[i+1]:
        ans += lst1[i]
print(ans+lst1[-1])