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

n, m = map(int, input().split())
s = input()
left = right = 0
base = ord("a") - 1
score = ord(s[0]) - base
mem = set()
for _ in range(m):
  com = input()
  if com == "L++":
    score //= 27
    left += 1
  elif com == "L--":
    left -= 1
    score = score * 27 + ord(s[left]) - base
  elif com == "R++":
    right += 1
    score += 27 ** (right - left) * (ord(s[right]) - base)
  elif com == "R--":
    score -= 27 ** (right - left) * (ord(s[right]) - base)
    right -= 1
  if score not in mem:mem.add(score)
print(len(mem))


### FIXED CODE ###

def main():
  n, m = map(int, input().split())
  s = input()
  mem = set()
  base = ord("a") - 1
  mod1 = 1000000007
  mod2 = 2147483647
  h1 = [0]
  h2 = [0]
  for c in s:
    h1.append((h1[-1] * 27 + ord(c) - base) % mod1)
    h2.append((h2[-1] * 27 + ord(c) - base) % mod2)
  pow_mem1 = {0:1}
  pow_mem2 = {0:1}
  def my_pow1(x):
    if x in pow_mem1:return pow_mem1[x]
    pow_mem1[x] = my_pow1(x - 1) * 27 % mod1
    return pow_mem1[x]

  def my_pow2(x):
    if x in pow_mem2:return pow_mem2[x]
    pow_mem2[x] = my_pow2(x - 1) * 27 % mod2
    return pow_mem2[x]
  
  left = right = 1
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    if com == "L--":
      left -= 1
    if com == "R++":
      right += 1
    if com == "R--":
      right -= 1
    x = (h1[right] - h1[left - 1] * my_pow1(right - left + 1)) % mod1
    y = (h2[right] - h2[left - 1] * my_pow2(right - left + 1)) % mod2
    mem.add((x, y))

  print(len(mem))

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

import itertools as it

def main():
    N=ii()
    L=lmis()
    ans=0
    for a,b,c in it.combinations(L,3):
        if a+b>c and a+c>b and b+c>a:
            ans+=1
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

import itertools as it

def main():
    N=ii()
    L=sorted(lmis(),reverse=True)

    ans=0
    for i in range(N-2):
        a=L[i]
        j=i+1
        k=N-1
        while j<k:
            if a<L[j]+L[k]:
                j+=1
                ans+=k-j+1
            else:
                k-=1
    
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    INF = 10**9+7
    A = list(map(int,input().split()))
    M = max(A)
    l = M.bit_length()
    d = [[0,0] for _ in range(l)]
    for i in range(N):
        num = A[i]
        count = 0
        while count != l:
            use = num%2
            d[count][use] += 1
            num //= 2
            count += 1
        
    ans = 0    
    for i in range(l):
        x,y = d[i]
        ans += (x*y)*(2**i)
        ans %= INF
        
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    a = np.array(list(map(int,input().split())),dtype = int)
    MOD = 10**9+7
    ans = 0
    for n in range(60):
        bit = (a>>n)&1
        nonzero = np.count_nonzero(bit)
        zero = N-nonzero
        count = nonzero*zero
        for _ in range(n):
            count *= 2
            count %= MOD
        ans += count
        ans %= MOD
    
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map( int, input().split() )
h_list = list( map( int, input().split() ) )
h_list.append(0)
result_list = [float("inf")]*N
result_list[0] = 0
for i in range(N):
    for j in range(1,min(K+1,N-i)):
        result_list[i+j] = min(result_list[i+j], result_list[i] + abs( ( h_list[i+j] - h_list[i]) ) )
print(result_list[N-1])

### FIXED CODE ###

N,K = map( int, input().split() )
H = list( map( int, input().split() ) )
dp = [0]*N
for i,Hi in enumerate(H[1:],1):
    s = max(0,i-K)
    dp[i] = min( [ t + abs( Hi - hl ) for hl,t in zip(H[s:i], dp[s:i]) ] )
print(dp[N-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
rev = 0
for q in qs:
    q = q.split()
    if q[0] == '1':
        rev = (rev+1) % 2
    else:
        if (q[1]=='1' and rev==0) or (q[1]=='2' and rev==1):
            S = q[2] + S
        else:
            S += q[2]
print(S if rev == 0 else S[::-1])

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def checkABC(x):
        if s[x]=='A' and s[x+1]=='B' and s[x+2]=='C':
            s[x],s[x+1],s[x+2]='B','C','A'
            return True
        else:
            return False
    
    s=list(input())
    N=len(s)
    i=0
    ans=0
    while True:
        if i >= N-2:
            break
        if checkABC(i) == True:
            if i!=0 and s[i-1]=='A':
                i-=2
            else:
                i+=1
            ans+=1
        i+=1
    print(ans)
        
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    s=input()
    s2=list(s.replace('BC','D'))
    N=len(s2)
    ans=0
    c=0
    for i in range(N):
        if s2[i]=='A':
            c+=1
        elif c!=0 and s2[i]=='D':
            ans+=c
        else:
            c=0
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M  = map(int, input().split())
AB = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    AB[i] = (a, b)
    
days_limit = M

jobs = AB[:]
jobs  =sorted(jobs, key=lambda x: x[1], reverse=True)
#print(jobs)

plan = [0] * (days_limit+1)

for d, r in jobs:
    while not d > days_limit:
        if plan[d] == 0:
            plan[d] = r
            break
        else:
            d += 1
#print(plan)
print(sum(plan))
    

### FIXED CODE ###

N, M  = map(int, input().split())
AB = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    AB[i] = (a, b)
    
days_limit = M

jobs = AB[:]
from collections import defaultdict
jobs_dict = defaultdict(lambda: [])
for d, r in jobs:
    jobs_dict[d].append(r)
#print(jobs_dict)

import heapq
hq = []

ans = 0
for d in range(1, M+1):
    for r in jobs_dict[d]:
        heapq.heappush(hq,-r)
    if hq:
        ans += -1 * heapq.heappop(hq)
print(ans)
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

cnt = 0
ans = [a[0], a[1]]
for i in range(n-1):
  num = a[i]
  tmp = a[i+1]
  for j in range(i+1, n):
    if abs(tmp-num/2) >= abs(a[j]-num/2):
      tmp = a[j]
    else:
      break
  if abs(tmp-num/2) < 1:
    ans = [num, tmp]
    break
  mul = math.factorial(num) // (math.factorial(tmp)*math.factorial(num-tmp))
  if cnt < mul:
    cnt = mul
    ans = [num, tmp]
print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

num = a[0]
tmp = a[1]
for j in range(1, n):
  if abs(tmp-num/2) >= abs(a[j]-num/2):
    tmp = a[j]
  else:
    break
ans = [num, tmp]
print(*ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
l = deque()
count ={}
for _ in range (n):
    cmd = input().split(' ')
    
    if cmd[0]=='insert':
        val = int(cmd[1])
        l.appendleft(val)
        if val not in count :
            count[val] =1
        else :
            count[val] +=1
                
    if cmd[0]=='delete':
        val = int(cmd[1])
        if len(l) !=0 and val in count:
           if count[val]:
            l.remove(val)
            count[val] -=1 
    
    if cmd[0]=='deleteFirst':
        val = l.popleft()
        count[val] -=1
    if cmd[0]=='deleteLast':
        val =l.pop()
        count[val] -=1
print(*l)


### FIXED CODE ###

from collections import deque
n = int(input())
l = deque()
for _ in range (n):
    cmd = input().split(' ')
    if cmd[0]=='insert':
        l.appendleft(cmd[1])  
    if cmd[0]=='delete':
        try:l.remove(cmd[1])
        except :pass
    if cmd[0]=='deleteFirst':
        l.popleft()
    if cmd[0]=='deleteLast':
        l.pop()
print(*l)
### BUGGY CODE ###


N,M = map(int, input().split(' '))
num = 0
for n in range(N):
    if (n == 0 and n+1 == N) or (n > 0 and n < N-1):
        if M < 2:
            num += 1
        else:
            num += M - 2 
print(num)

### FIXED CODE ###


import sys

N,M = map(int, input().split(' '))
num = 0
if N == 1:
    if M < 2:
        print(1)
        sys.exit()
    print(str(M-2))
    sys.exit()
elif N == 2:
    print(0)
    sys.exit()
else:
    if M < 2:
        num = N-2
    else:
        num = (M-2)*(N-2) 
    print(num)
### BUGGY CODE ###

import itertools
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
ll=[i for i in range(1,n+1)]
x=[]
for i in range(1,n+1):
    z=list(itertools.combinations(l,i))
    zz=list(itertools.combinations(ll,i))
    for j in range(len(z)):
        x.append([sum(z[j]),(i-1)*10,list(zz[j])])
x.sort()
#print(x)
A=[];B=[];C=[]
for i in range(len(x)):
    A.append([x[i][1]+abs(a-x[i][0]),x[i][2]])
    B.append([x[i][1]+abs(b-x[i][0]),x[i][2]])
    C.append([x[i][1]+abs(c-x[i][0]),x[i][2]])
A.sort();B.sort();C.sort()
m=len(A)
ans=float('inf')
for i in range(m):
    for j in range(m):
        for k in range(m):
            if len(A[i][1]+B[j][1]+C[k][1])!=len((set(A[i][1]+B[j][1]+C[k][1]))):
                continue
            else:
                #print(A[i][1]+B[j][1]+C[k][1])
                ans=min(ans,A[i][0]+B[j][0]+C[k][0])
print(ans)
                
    

### FIXED CODE ###

import itertools
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
l.sort()
ll=[i for i in range(1,n+1)]
x=[]
for i in range(1,n+1):
    z=list(itertools.combinations(l,i))
    zz=list(itertools.combinations(ll,i))
    for j in range(len(z)):
        x.append([sum(z[j]),(i-1)*10,list(zz[j])])
x.sort()
#print(x)
A=[];B=[];C=[]
for i in range(len(x)):
    A.append([x[i][1]+abs(a-x[i][0]),x[i][2]])
    B.append([x[i][1]+abs(b-x[i][0]),x[i][2]])
    C.append([x[i][1]+abs(c-x[i][0]),x[i][2]])
A.sort();B.sort();C.sort()
#print(A)
#print(B)
#print(C)
m=len(A)
ans=float('inf')
for i in range(m):
    for j in range(m):
        for k in range(m):
            if len(A[i][1]+B[j][1]+C[k][1])>=9:
                break
            elif len(A[i][1]+B[j][1]+C[k][1])==len((set(A[i][1]+B[j][1]+C[k][1]))):
                ans=min(ans,A[i][0]+B[j][0]+C[k][0])
print(ans)
### BUGGY CODE ###

S = input()
pre, post = [], []
Q = int(input())
reversed = False
for _ in range(Q):
  query = input().split()
  if query[0] == '1':
    reversed = not reversed
    pre, post = post[::-1], pre[::-1]
  else:  # query[0] == 2
    F, C = query[1:]
    if F == '1':
      pre = [C] + pre
    else:  # F == '2'
      post.append(C)
if reversed:
  print(''.join(pre) + S[::-1] + ''.join(post))
else:
  print(''.join(pre) + S + ''.join(post))

### FIXED CODE ###

from collections import deque

S = input()
pre, post = deque(), deque()
Q = int(input())
reversed = False
for _ in range(Q):
  query = input().split()
  if query[0] == '1':
    reversed = not reversed
    pre, post = post, pre
  else:  # query[0] == 2
    F, C = query[1:]
    if F == '1':
      if reversed:
        pre.append(C)
      else:
        pre.appendleft(C)
    else:  # F == '2'
      if reversed:
        post.appendleft(C)
      else:
      	post.append(C)
if reversed:
  print(''.join(pre)[::-1] + S[::-1] + ''.join(post)[::-1])
else:
  print(''.join(pre) + S + ''.join(post))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

N = int(input())

G =[[] for _ in range(N + 1)] #iさんが勝った相手のリストを要素とするリスト
for i in range(2, N + 1):
    a = int(input())
    G[a].append(i)

# print (G)

set_lst = [set() for _ in range(N + 1)] #使った数字を管理する
tmp_lst = [0] * (N + 1) #次に使える最小を管理する

# print (set_lst)
# print (tmp_lst)

def calc(x): #xからの移動先を検討
    tmp = 0 #何試合目に行うことができるか
    for next_ in G[x]:
        y = max(calc(next_), tmp_lst[x])
        while y in set_lst[x]: #既に使われていたとき、一つずつ更新する
            y += 1
        set_lst[x].add(y) #新しく使ったことを記録する
        if y == tmp_lst[x]:
            tmp_lst[x] = y + 1
        tmp = max(y, tmp)
    return tmp + 1

ans = calc(1) - 1

# print (set_lst)
# print (tmp_lst)
print (ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

N = int(input())

G =[[] for _ in range(N + 1)] #iさんが勝った相手のリストを要素とするリスト
for i in range(2, N + 1):
    a = int(input())
    G[a].append(i)

# print (G)

def calc(x): #xからの移動先を検討
    tmp = 0
    lst = []
    for next_ in G[x]:
        y = calc(next_)
        lst.append(y)
    lst.sort()
    for i in lst:
        if tmp >= i:
            tmp += 1
        else: #tmp < i
            tmp = i
    return tmp + 1

ans = calc(1) - 1

print (ans)
### BUGGY CODE ###

def nibutan(n, M):
  ok = 0
  ng = M + 1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    #print("value:", mid)
    if nasu(mid) >= n:
      ok = mid
    else:
      ng = mid
  return ok

def nasu(x):
  ans = 0
  for i in A:
    #print("L:", i, end = " ")
    t = N - hogetan(x - i)
    #print("n:", t)
    ans += t
  return ans

def hogetan(n):
  ok = N
  ng = -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if A[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))


A.sort()
MAX = A[-1] + A[-1]
inf = MAX + 10

t = nibutan(M, MAX)
mi = inf
cnt = 0
ans = 0
for i in A:
  k = hogetan(t - i)
  n = N - k
  cnt += n
  if n != 0:
    mi = min(mi, i + A[k])
  ans += n * 2 * i

ans -= mi * (cnt - M)

print(ans)

### FIXED CODE ###

def nibutan(n, M):
  ok = 0
  ng = M + 1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    #print("value:", mid)
    if nasu(mid) >= n:
      ok = mid
    else:
      ng = mid
  return ok

def nasu(x):
  ans = 0
  for i in A:
    #print("L:", i, end = " ")
    t = N - hogetan(x - i)
    #print("n:", t)
    ans += t
  return ans

def hogetan(n):
  ok = N
  ng = -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if A[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))


A.sort()
MAX = A[-1] + A[-1]
inf = MAX + 10

t = nibutan(M, MAX)
mi = inf
cnt = 0
ans = 0
for i in A:
  k = hogetan(t - i)
  n = N - k
  cnt += n
  if n != 0:
    mi = min(mi, i + A[k])
  ans += n * 2 * i

ans -= mi * (cnt - M)

print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

aa = [0]*(N+1)
for i in range(1, N+1):
    aa[i] = aa[i-1]+A[i-1]

bb = [0]*(M+1)
for i in range(1, M+1):
    bb[i] = bb[i-1]+B[i-1]

ans = 0
for i in range(N+1):
    tmp_K = K-aa[i]
    if tmp_K == 0:
        ans = max(ans, i)
    elif tmp_K < 0:
        continue
    mn = 0
    mx = M
    while True:
        if mn == mx:
            if tmp_K >= bb[mn]:
                ans = max(ans, i+mn)
            break

        mid = (mn+mx//2)
        if bb[mid] <= tmp_K:
            if mn == mid:
                mn = mid+1
            else:
                mn = mid
        else:
            if mx == mid:
                mx = mid-1
            else:
                mx = mid
print(ans)


### FIXED CODE ###

import itertools
import bisect

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

aa = [0] + list(itertools.accumulate(A))
bb = [0] + list(itertools.accumulate(B))

ans = bisect.bisect_left(aa, K)-1
ans = max(ans, bisect.bisect_left(bb, K)-1)

for i in reversed(range(N+1)):
    tmp_K = K-aa[i]
    if tmp_K == 0:
        ans = max(ans, i)
    elif tmp_K < 0:
        continue

    if i + M <= ans:
        continue

    if tmp_K >= bb[-1]:
        ans = max(ans, i+M)
        continue

    ans = max(ans, bisect.bisect_left(bb, tmp_K)-1+i)
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for A in range(1, N+1):
    for B in range(A, N+1):
        str_A = str(A)
        str_B = str(B)
        if str_A[-1] == str_B[0] and str_A[0] == str_B[-1]:
            # print(A, B)
            ans += 1
            if A != B:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
cij = [[0 for _ in range(10)] for _ in range(10)]
for i in range(1, N+1):
    A = str(i)
    cij[int(A[0])][int(A[-1])] += 1
ans = 0
for i in range(10):
    for j in range(10):
        ans += cij[i][j] * cij[j][i]
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
cnt =[]
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            cnt.append(s[i]+s[j]+s[k])
print(len(set(cnt)))

### FIXED CODE ###

import math,time
N = int(input())
S = input()

ans = 0
for i in range(1000):
    locknum = str(i).zfill(3)
    a = S.find(locknum[0])
    b = S.find(locknum[1],a+1)
    c = S.find(locknum[2],b+1)
    if a!=-1 and b!=-1 and c!=-1:
        # print(i)
        ans +=1


             
print(ans)
### BUGGY CODE ###

t = input()
ans = ""
for i in range(len(t)):
    if t[i] == '?':
        ans += 'D'
    else:
        ans += t[i]
print(ans)

### FIXED CODE ###

print(input().replace('?','D'))
### BUGGY CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
A_array = list(map(int, input().split()))
B_array = list(map(int, input().split()))
C_array = list(map(int, input().split()))

A_array.sort()
B_array.sort()
C_array.sort()

use_array = [[[0] * Z for i in range(Y)] for i in range(X)]
sum_array = []

candidate = []

max_sum = A_array[-1] + B_array[-1] + C_array[-1]

heapq.heappush(candidate, (0, X - 1, Y - 1, Z - 1))

for i in range(K):

    s, x, y, z = heapq.heappop(candidate)

    sum_array.append(s)
    if x != 0 and use_array[x - 1][y][z] == 0:
        use_array[x - 1][y][z] = 1
        diff = A_array[x] - A_array[x - 1]
        heapq.heappush(candidate, (s + diff, x - 1, y, z))

    if y != 0 and use_array[x][y - 1][z] == 0:
        use_array[x][y - 1][z] = 1
        diff = B_array[y] - B_array[y - 1]
        heapq.heappush(candidate, (s + diff, x, y - 1, z))

    if z != 0 and use_array[x][y][z - 1] == 0:
        use_array[x][y][z - 1] = 1
        diff = C_array[z] - C_array[z - 1]
        heapq.heappush(candidate, (s + diff, x, y, z - 1))

for ans in sum_array:
    print(max_sum - ans)

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
A_array = list(map(int, input().split()))
B_array = list(map(int, input().split()))
C_array = list(map(int, input().split()))

A_array.sort()
B_array.sort()
C_array.sort()

use_array = []
sum_array = []

candidate = []
heapq.heapify(candidate)

max_sum = A_array[-1] + B_array[-1] + C_array[-1]

heapq.heappush(candidate, (0, X - 1, Y - 1, Z - 1))
use_array.append((X - 1, Y - 1, Z - 1))

for i in range(K):
    s, x, y, z = heapq.heappop(candidate)

    sum_array.append(s)
    if x != 0 and (x - 1, y, z) not in use_array:
        use_array.append((x - 1, y, z))
        diff = A_array[x] - A_array[x - 1]
        heapq.heappush(candidate, (s + diff, x - 1, y, z))

    if y != 0 and (x, y - 1, z) not in use_array:
        use_array.append((x, y - 1, z))
        diff = B_array[y] - B_array[y - 1]
        heapq.heappush(candidate, (s + diff, x, y - 1, z))

    if z != 0 and (x, y, z - 1) not in use_array:
        use_array.append((x, y, z - 1))
        diff = C_array[z] - C_array[z - 1]
        heapq.heappush(candidate, (s + diff, x, y, z - 1))

for ans in sum_array:
    print(max_sum - ans)
### BUGGY CODE ###

n=int(input())
a=[0]*n
def int1(x):
  return int(x)-1
a[:]=map(int1,input().split())
#print(a)
r=0
for ii in range(n):
  if ii in a:
    del a[0:a.index(ii)]
    r+=1
    #print(a,r)
  else:
    #print(a)
    if r==0:
      print(-1)
    else:
      print(n-r)
    exit()
print(n-r)

### FIXED CODE ###

n=int(input())
a=[0]*n
def int1(x):
  return int(x)-1
a[:]=map(int1,input().split())

r=0
#j0=0
#import numpy as np
ii=0
for jj in range(n):
  if a[jj]==ii:
    r+=1
    ii+=1
if r==0:
  print(-1)
  exit()

print(n-r)
### BUGGY CODE ###

n = int(raw_input())
a = raw_input().split()

cnt = 0
for i in a:
    a[cnt] = int(i)
    cnt += 1

chk = {}
def make_divisors(k):
    divisors = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            if i in chk:
                chk[i] += 1
            else:
                chk[i] = 1
            if i != k // i:
                key = int(k//i)
                if key in chk:
                    chk[key] += 1
                else:
                    chk[key] = 1

    return divisors

if n == 2:
    print max(a[0],a[1])
else:
    for i in range(2):
        make_divisors(a[i])
    cnt = 1
    for i in range(2,len(a)):
        k = a[i]
        del_list = []
        for j in chk:
            if k % j == 0:
                chk[j] += 1
            if chk[j] < cnt+1:
                del_list.append(j)
        for j in del_list:
            del chk[j]
        cnt += 1

    answer = max(chk.keys())
#    answer = 0
#    for i in chk:
#        if int(chk[i]) >= n - 1 and i > answer:
#            answer = i
    print answer

### FIXED CODE ###

n = int(raw_input())
a = raw_input().split()

cnt = 0
for i in a:
    a[cnt] = int(i)
    cnt += 1

chk = {}
chk2 = {}
def make_divisors(k):
    divisors = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            if i in chk:
                chk[i] += 1
            else:
                chk[i] = 1
            if i != k // i:
                key = int(k//i)
                if key in chk:
                    chk[key] += 1
                else:
                    chk[key] = 1
    return divisors

for i in range(2):
    make_divisors(a[i])
cnt = 1
for i in range(2,len(a)):
    k = a[i]
    if k not in chk2:
        chk2[k] = 1
    else:
        if chk2[k] == 1:
            chk2[k] += 1
        elif chk2[k] > 1:
            continue
    del_list = []
    for j in chk:
        if k % j == 0:
            chk[j] += 1
        if chk[j] < cnt+1:
            del_list.append(j)
    for j in del_list:
        del chk[j]
    cnt += 1

answer = 0
for i in chk:
    if int(chk[i]) >= chk[1] - 1 and i > answer:
        answer = i
print answer
### BUGGY CODE ###

import heapq as hp

n,q=[int(x) for x in input().rstrip().split()]

l=[[] for i in range(n)]
ans=[0]*n

for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  
  que=[0]
  done=[0]*n  

  while(que):
    now=que.pop(0)
    if done[now]==1:
      continue
    done[now]=1

    for i in l[now]:
      if done[i]==0:
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)


### FIXED CODE ###

n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
ans=[0]*n

for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop()

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)