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

Solution (Python):





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



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



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


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:
            
            pre_max = max(pre_max-1, 0)
            pre = num
    else:
        print(-1)
        sys.exit()
print(ans)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):



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

if __name__ == '__main__':
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


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


def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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




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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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):
  
  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] 
      ans += prev
    else:
      print(-1)
      exit()
print(ans)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):



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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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())

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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: 
        ans+=last
        last=a[i]

ans+=last
print(ans)

Solution (Python):
import math
import fractions



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

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]  
factinv = [1, 1]  
inv = [0, 1]  

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)

'''










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)

Solution (Python):
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)

Solution (Python):

"""
問題：
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])

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

if __name__ == "__main__":
    main()

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

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

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

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

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

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

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

tmp = 0
ans = 0
for i in range(1,N):
    if A[i] < tmp+1:
        ans += tmp
    tmp = A[i]

ans += tmp

print(ans)

Solution (Python):
N=int(input())
a=t=-1
for i in range(N):
 A=int(input())
 if t+1<A:
  a=-1
  break
 if t+1==A:a+=1
 else:a+=A
 t=A
print(a)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    if A[0]!=0:
        print(-1)
        sys.exit()
    dp=[0]*n
    for i,a in enumerate(A[1:],1):
        if a>=A[i-1]+2:
            print(-1) 
            sys.exit()
        elif a==A[i-1]+1:
            dp[i]=1
        else:
            dp[i]=a
    print(sum(dp))

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    if A[0]!=0:
        print(-1)
        sys.exit()
    dp=[0]*n
    for i,a in enumerate(A[1:],1):
        if a>=A[i-1]+2:
            print(-1) 
            sys.exit()
        elif a==A[i-1]+1:
            dp[i]=1
        else:
            dp[i]=a
    print(sum(dp))

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
a=-1
t=-1
for i in range(N):
    A=int(input())
    if t+1<A:
        a=-1
        break
    if t+1==A:
        a+=1
    else:
        a+=A
    t=A
print(a)

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

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

Solution (Python):

N=int(input())
a=[int(input()) for _ in range(N)]
answer=0
now_value=10**9
for i in range(N-1,-1,-1):
    if a[i]>i:
        answer=-1
        break 
    if a[i]==now_value-1:
        now_value-=1
    else:
        answer+=a[i]
        now_value=a[i]
for i in range(N-1):
    if a[i+1]-a[i]>1:
         answer=-1
         break
print(answer)

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

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

cur=0
ans=0
for a in A:
    if a<=cur:
        ans+=a
    elif a==(cur+1):
        ans+=1
    else:
        print(-1)
        exit()
    cur=a

print(ans)

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

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

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



main()