Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
ans=[]
n=int(raw_input())
for _ in range(n):
    a=raw_input().split()
    if a[0]=='insert': ans.insert(0,a[1])
    elif a[0]=='deleteFirst': del ans[0]
    elif a[0]=='deleteLast': del ans[-1]
#    else: ans.remove(str(a[1]))
    else:
        if a[1] in ans:
            ans.remove(a[1])
#    print ans
print ' '.join(ans)

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
### BUGGY CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

str_list = stdin.readline().rstrip().split()
int_list = int_data = [int(i) for i in str_list]

cnt_list = [int_list.count(i) for i in range(1, N+1)]
ret_list = []

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] < 2:
        continue
    else:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2

for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list.append(tmp_ret)

for i in int_list:
    print(ret_list[i-1])

### FIXED CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))
cnt_list = [0] * N

for i in int_list:
    cnt_list[i-1] += 1

ret_list = [0] * N

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] > 1:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2


for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list[i] = tmp_ret

for i in int_list:
    print(ret_list[i-1])
### BUGGY CODE ###

from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

if m != 0:
    lin = [int(stdin.readline().rstrip()) for _ in range(m)]
else:
    lin = [-1]

dp = [-1]*(n+1)
dp[0] = 1

if lin[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if i in lin:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))

### FIXED CODE ###

from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

lin = [0]*(n+1)

if m != 0:
    for i in range(m):
        lin[int(stdin.readline().rstrip())] = -1

dp = [-1]*(n+1)

dp[0] = 1

if lin[1] == -1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if lin[i] == -1:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))
### BUGGY CODE ###

import math
k = int(input())
sum_gcd = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):

            sum_gcd += math.gcd(math.gcd(a,b) , c)

print(sum_gcd)

### FIXED CODE ###

import math
k = int(input())
sum_gcd = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):

            sum_gcd += math.gcd(math.gcd(a,b) , c)

print(sum_gcd)
### BUGGY CODE ###

N=input()
S=input()
R=[]
G=[]
B=[]
for i in range(len(S)):
    if S[i]=='R':
        R.append(i)
    if S[i]=='G':
        G.append(i)
    if S[i]=='B':
        B.append(i)

count=0
for i in range(len(R)):
    for j in range(len(G)):

        if max(R[i],G[j])+abs(R[i]-G[j]) in B:
            count+=1

        if min(R[i],G[j])-abs(R[i]-G[j]) in B:
            count+=1

        if (R[i]+G[j])/2 in B:
            count+=1


print(str((len(R)*len(G)*len(B))-count))


### FIXED CODE ###

N=input()
S=input()
Sn=[]
R=0
G=0
B=0
for i in range(len(S)):
    if S[i]=='R':
        R+=1
        Sn.append(1)
    elif S[i]=='G':
        G+=1
        Sn.append(2)
    else:
        B+=1
        Sn.append(3)

count=0
for start in range(len(S)):
        for diff in range(1,int((len(S)-start+1)/2)):
            #int(start,diff)
            if (Sn[start]-Sn[start+diff])*(Sn[start+diff]-Sn[start+(2*diff)])*(Sn[start]-Sn[start+(2*diff)])!=0: 
                count+=1
                
print(str((R*G*B)-count))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        return 2
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            return f
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
        return n
    return n

A_B = prime_factorize(X)
A_B_other = X // A_B
A = 0
while True:
    B = A - A_B

    if A ** 5 - B ** 5 == X:
        print(A, int(B))
        exit()
    B = A - A_B_other

    if A ** 5 - B ** 5 == X:
        print(A, int(B))
        exit()

    A += 1

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

for a in range(2000):
    A = a - 1000

    for b in range(2000):
        B = b - 1000
        if A ** 5 - B ** 5 == X:
            print("{} {}".format(A, B))
            exit()
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = []
for i in range(N):
  cnt = S[0:i].count('W')
  cnt += S[i+1:N+1].count('E')
  ans.append(cnt)
print(min(ans)) 

### FIXED CODE ###

N = int(input())
S = list(input())
E = S.count('E')
ans = []
prev = E
pS = 'E'
for i in range(N):
  if S[i] == 'W':
    current = prev
  elif S[i] == 'E':
    current = prev - 1
  if pS == 'W':
    current += 1
  ans.append(current)
  prev = current
  pS = S[i]
print(min(ans))
### BUGGY CODE ###

s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False

for i in range(n - k + 1):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue

    for j in range(1,k):
        if p[i - 1] > p[i + j - 1] or p[i + k - 1] < p[i + j - 1]:
            num += 1
            break
    

print(num)


### FIXED CODE ###

class MinSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p
        self.start_idx = 0

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 >= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                self.start_idx += 1
            else:
                break

    def min(self):
        pos1 = self.pos_list[self.start_idx]
        val1 = self.val_list[pos1]
        return val1

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p
        self.start_idx = 0
        
    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 <= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                del self.pos_list[self.start_idx]
            else:
                break

    def max(self):
        pos1 = self.pos_list[self.start_idx]
        val1 = self.val_list[pos1]
        return val1




s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 1
ident = True
rv_pos = -1

minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)

for i in range(k - 1):
    if p[i] > p[i + 1]:
        rv_pos = i
        ident = False
    
for i in range(k-1):
    minw.put(i)
    maxw.put(i)

for i in range(1,n - k + 1):
    
    maxw.put(i + k - 2)
    minw.put(i + k - 2)
    maxw.get(i-1)
    minw.get(i-1)

    """    
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue
    """
    if p[i + k - 2] > p[i + k - 1]:
        rv_pos = i + k - 2
        

    
    if rv_pos < i:
        if not ident:
            ident = True
            num += 1
        continue
            

    if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
        num += 1

    
print(num)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(1000):
  pin = '{:03d}'.format(i)
  j = 0
  for si in s:
    if si == pin[j]:
      j+=1
      if j==3:
        break        
  if j == 3:
    ans+=1
    
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = 0
for i in range(1000):
  pin = '{:03d}'.format(i)
  p1 = s.find(pin[0])
  if p1>=0:    
    p2 = s[p1+1:].find(pin[1])     
    if p2>=0:
      p3 = s[p1+p2+2:].find(pin[2])      
      if p3>=0:
        ans+=1        
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


if __name__ == '__main__':
    num_person = int(input())
    height_list = list(map(int, input().split()))
    height_list = [0] + height_list # var[0] is dummy
    count = 0
    for i in range(1, len(height_list)):
        h_i = height_list[i]
        #if h_i > num_person:
        #    continue
        for j in range(i + 1, len(height_list)):
            #print(i, j) # debug
            h_j = height_list[j]
            if j - i == h_j + h_i:
                count += 1
    #print('count') # debug
    #print(count) # debug
    print(count)

    #print('\33[32m' + 'end' + '\033[0m') # debug


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Counter(dict):

    def __init__(self, l=None):
        if l is None:
            return
        for e in l:
            self[e] += 1

    def __missing__(self, key):
        self[key] = 0
        return self[key]

def make_i_list(height_list):
    i_list = [0] * len(height_list) # [0] is dummy
    for i, h in enumerate(height_list):
        i_list[i] = h + i
    i_list.pop(0) # delete dummy
    return i_list

def make_j_list(height_list):
    j_list = [0] * len(height_list) # [0] is dummy
    for j, h in enumerate(height_list):
        j_list[j] = - h + j
    j_list.pop(0) # delete dummy
    return j_list

def make_same_ij_person_dict(i_list, j_list, same_ij_person_dict):
    for key in range(1, len(i_list)): # skip 0 because dummy
        if i_list[key] == j_list[key]:
            value = i_list[key]
            same_ij_person_dict[value] += 1


if __name__ == '__main__':
    num_person = int(input())
    height_list = [0] + list(map(int, input().split())) # [0] is dummy
    i_list = make_i_list(height_list)
    j_list = make_j_list(height_list)
    i_dict = Counter(i_list) # var[value] = count
    j_dict = Counter(j_list) # var[value] = count
    # there is no person that i_list[key] == j_list[key]
    #print('i_list') # debug
    #print(i_list) # debug
    #print(i_dict) # debug
    #print('j_list') # debug
    #print(j_list) # debug
    #print(j_dict) # debug
    ans_count = 0
    for value in i_dict.keys():
        if value in j_dict.keys():
            ans_count += i_dict[value] * j_dict[value]
    print(ans_count)


    #print('\33[32m' + 'end' + '\033[0m') # debug
### BUGGY CODE ###

q=int(input())
import math
def is_prime(n):
    if n==1:return False
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True
ko0=[]
ko=[]
for i in range(1,10**5,2):
    if is_prime((i+1)//2)==True:
        ko0.append(i)  
for i in ko0:
    if is_prime(i)==True:
        ko.append(i)
for i in range(q):
    l,r=map(int,input().split())   
    ans0=1
    ans1=0
    for i in range(len(ko)):
        if l<=ko[i]:
            ans0=i
            break
    for i in range(len(ko)):
        if r<ko[i]:
            ans1=i-1
            break
    print(ans1-ans0+1)

### FIXED CODE ###

q=int(input())
import math
import numpy as np
def is_prime(n):
    if n==1:return False
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True
def is_is_prime(n):
    an=0
    if is_prime((n+1)//2)==True:
        if is_prime(n)==True:
            an=1
    return an
ko=[]
for i in range(1,10**5,2):
    ko.append(is_is_prime(i))

koko=np.cumsum(ko)

for i in range(q):
    l,r=map(int,input().split()) 
    if l==1:
        ans=koko[(r-1)//2]-koko[(l-1)//2]
    else:
        ans=koko[((r-1)//2)]-koko[((l-1)//2)-1]
    print(ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))


find = False
# 2こめ
for i, x in enumerate(li[1:]):
    result = [li[0]]
    
    result.append(x)
    not_used = li[1:]
    not_used.pop(i)
    
    # 3こめ~
    for j in range(n - 2):
#         print(result)
        nex = result[-1]^result[-2]
#         print(nex, not_used)
        if nex in not_used:
            idx = not_used.index(nex)
            result.append(nex)
            not_used.pop(idx)
        else:
            break
    if len(result) != n:
        continue
    else:
        print("Yes")
        find = True
        break

if not find:
    print("No")
        
        

### FIXED CODE ###

import numpy as np
n = int(input())
li = np.array(list(map(int, input().split())))

if np.count_nonzero(li) == 0:
    print("Yes")
elif len(li)%3 != 0:
    print("No")
else:
    li = sorted(li)
    li0 = li[:n//3]
    li1 = li[n//3:n//3*2]
    li2 = li[n//3*2:]
    if (li0 == li0[0]).all() and (li1 == li1[0]).all() and (li2 == li2[0]).all() and ((li0[0]^li1[0]) == li2[0] or (li0[0]^li1[0]) == li2[0] or (li0[0]^li1[0]) == li2[0]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

import sys
input = sys.stdin.buffer.readline
from math import hypot
def main():
	sx, sy, gx, gy = map(int, input().split())
	n = int(input())
	v = [(sx, sy, 0), (gx, gy, 0)]
	for _ in range(n):
		v.append(tuple(map(int, input().split())))
	con = [[] for _ in range(n + 2)]
	for i, p1 in enumerate(v):
		for j, p2 in enumerate(v[i + 1:]):
			t = max(0, hypot(p1[0] - p2[0], p1[1] - p2[1]) - p1[2] - p2[2])
			con[i].append((i + j + 1, t))
			con[i + j + 1].append((i, t))
	print(Dijkstra(con)[1])

if __name__ == '__main__':
	main()

### FIXED CODE ###

from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

import sys
input = sys.stdin.buffer.readline
from math import hypot
sx,sy,gx,gy=map(int,input().split())
n=int(input())
v=[(sx,sy,0),(gx,gy,0)]
for _ in range(n):
	v.append(tuple(map(int,input().split())))
con=[[] for _ in range(n+2)]
for i,p1 in enumerate(v):
	for j,p2 in enumerate(v[i+1:]):
		t=max(0,hypot(p1[0]-p2[0],p1[1]-p2[1])-p1[2]-p2[2])
		con[i].append((i+j+1,t))
		con[i+j+1].append((i,t))
print(Dijkstra(con)[1])
### BUGGY CODE ###

import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[int(input()) for i in range(m)]
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
else:dp[1]=0 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1
#print(a,b,l)
for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)
### BUGGY CODE ###

g=lambda x,y:x if y<1else g(y,x%y)
_,a=open(0)
*a,=map(int,a.split())
s=1
for t in a:s*=t//g(s,t)
print(sum(s//i for i in a)%(10**9+7))

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

# AtCoder
A, B, K = map(int, input().split())


rn = range(A, B+1)
ln = len(rn)
if K > ln:
    for i in rn:
        print(i)
    exit()

for i, e in enumerate(rn, 1):
    if K >= i:
        print(e)
    elif ln - K < i:
        print(e)


### FIXED CODE ###

# AtCoder
A, B, K = map(int, input().split())
for i in range(A, min(A+K, B+1)):
    print(i)
for j in range(max(B-K+1, A+K), B+1):
    print(j)
### BUGGY CODE ###

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

dp = [[0] * (N+1) for i in range(N+1)]
for s in range(1, N+1):
    for l in range(N-s+1):
        r = l + s
        if (N - s) % 2 == 0:
            dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
        else:
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
    
print(dp[0][N])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())
### BUGGY 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)

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

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

result = 0

if a[n-1] != 0:
    result += a[n-1]

for i in range(2, n):
    j = n - i
    if a[j] != 0 and a[j] != a[j + 1] - 1:
            result += a[j]

print(result)