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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    def g(a):
        l = len(a)
        if l == 0:
            return 0
        if l == 1:
            return a[0]
        m = min(a)
        i = a.index(m)
        return (i+1) * (l-i) * m + g(a[i+1:]) + g(a[:i])
    return g(a)

print(f())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    l = list(range(n+2))
    r = list(range(n+2))
    b = [0]*(n+2)
    for i, x in enumerate(a, 1):
        b[x] = i
    c = 0
    for i in range(n,0,-1):
        bi = b[i]
        c += i * (r[bi] - bi + 1) * (bi - l[bi] + 1)
        r[l[bi]-1] = r[bi]
        l[r[bi]+1] = l[bi]
    return c

print(f())
### BUGGY CODE ###

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

# print(N, A)
B = [0]*N

for i in range((N + 1)//2, N + 1):
    B[i - 1] = A[i - 1]

for i in range(N // 2):
    index = N // 2 - i - 1
    num = 0
    for j in range(N):
        v = N - j - 1
        if (v + 1) % (index + 1) == 0:
            num += B[v]
    if num % 2 != A[index]:
        B[index] = 1
# print(B)

M = 0
for b in B:
    if b == 1:
        M += 1
print(M)
ANS = []
for i in range(N):
    if B[i] == 1:
        ANS.append(str(i + 1))
if M > 0:
    ans = ' '.join(ANS)
    print(ans)


### FIXED CODE ###

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

# print(N, A)
B = [0]*N

for i in range(N//2 + 1, N + 1):
#     print(i, A[i - 1])
    B[i - 1] = A[i - 1]

for i in range(N // 2):
    index = N // 2 - i - 1
    num = 0
#     print(index)
    for j in range(1, N // (index + 1) + 1):
        v = j * (index + 1) - 1
        num += B[v]
        # print(v, B[v])
#     print(index, num)
    if num % 2 != A[index]:
        B[index] = 1
# print(B)

M = 0
for b in B:
    if b == 1:
        M += 1
print(M)
ANS = []
for i in range(N):
    if B[i] == 1:
        ANS.append(str(i + 1))
if M > 0:
    ans = ' '.join(ANS)
    print(ans)
### BUGGY CODE ###

N = int(input())
inputA = input()
listA = inputA.split(' ')
count = 0
for num in listA:
    k = listA.count(num)
    if k != 1:
        print('NO')
        break
    else:
        count += 1
if count == N:
    print('YES')

### FIXED CODE ###

N = int(input())
inputA = input()
listA = inputA.split(' ')
listA.sort()
output = 'YES'
for i in range (len(listA) - 1):
    if listA[i] == listA[i + 1]:
        output = 'NO'
print(output)
### BUGGY CODE ###

def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {}
        d[s] = 0
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            if point in d:
                continue
            d[point] = dist
            if point == g:
                return dist
            for nextdist, nextp in edge[point]:
                if not nextp in d:
                    heapq.heappush(queue, (dist + nextdist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append((1, q))
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextp in edge[point]:
                if not nextp in d:
                    if not -1 in point or -1 in nextp:
                        queue.appendleft((dist, nextp))
                    else:
                        queue.append((dist + 1, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, c)].add((q, c))
        edge[(q, c)].add((p, c))
        edge[(p, c)].add((p, -1))
        edge[(q, c)].add((q, -1))
        edge[(p, -1)].add((p, c))
        edge[(q, -1)].add((q, c))
    print(Dijkstra((0, -1), (n - 1, -1)))


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

import sys
sys.setrecursionlimit(10**7) 

def dfs(G,v,p):
    if v != p and p != -1:
        counter[v]+=counter[p]

    for next in G[v]:
        if next == p:
            continue
        dfs(G,next,v)
    

N,Q = map(int, input().split())
counter = [0]*N
G = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

#print(subtree)
for _ in range(Q):
    p,x = map(int, input().split())
    p-=1
    counter[p]+=x
dfs(G,0,-1)
counter = map(str,counter)
print(' '.join(counter))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7) 

def dfs(G,v,p):
    for next in G[v]:
        if next == p:
            continue
        counter[next]+=counter[v]
        dfs(G,next,v)
    

N,Q = map(int, input().split())
counter = [0]*N
G = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

#print(subtree)
for _ in range(Q):
    p,x = map(int, input().split())
    p-=1
    counter[p]+=x
dfs(G,0,-1)
counter = map(str,counter)
print(' '.join(counter))
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
  cmd = input()
  if cmd[0] == '1':
    s = s[::-1]
  else:
    t,f,c = cmd.split()
    if f == '1':
      s = c + s
    else:
      s = s + c
print(s)
    

### FIXED CODE ###

from collections import deque
s = input()

q = int(input())
s = deque(s)
r = False
for _ in range(q):
    cmd = input()
    if cmd[0] == '1':
        r = not r
    else:
        cmd, f, c = cmd.split()
        if (f == '2' and not r) or (f=='1' and r):
            s.append(c)
        else:
            s.appendleft(c)
if r:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

for j, a in enumerate(A):
  if a:
    B[0] += 1
    temp = 1
    for i in range(p-1, -1, -1):
      B[i] -= (-1)**(i%2) * temp * comb(p-1, i)
      temp *= j
      temp %= p
      B[i] %= p
print(*B)

### FIXED CODE ###

import sys
input = sys.stdin.readline

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

for j, a in enumerate(A):
  if a:
    B[0] += 1
    temp = 1
    for i in range(p-1, -1, -1):
      B[i] -= (-1)**(i%2) * temp * comb(p-1, i)
      temp *= j
      temp %= p
      B[i] %= p
print(*B)
### BUGGY CODE ###

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
a = S[-1]
dp = np.zeros((n, 26), int)
x_ = dp[0]
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x_[0:10] += 1
else:
    x_[int(a)] += 1
x_[13:] = x_[:13]
for s, x, l_ in zip(S[-2::-1], dp[1:], l[1:]):
    if s == "?":
        x[:13] += sum([x_[v:v+13] for v in l_])
    else:
        v = l_[int(s)]
        x[:13] += x_[v:v+13]
    x %= mod
    x[13:] = x[:13]
    x_ = x
print(x_[5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

n=int(input())
d=list(map(int,input().split()))
d=sorted(d)

ans=0
for i in range(1,d[-1]+1):
    cnt=0
    for j in range(n):
        if i>d[j]:
            cnt+=1
        else:
            break
    if n-cnt==cnt:
        ans+=1
print(ans)

### FIXED CODE ###

import bisect

n=int(input())
d=list(map(int,input().split()))
d=sorted(d)

ans=0
for i in range(1,d[-1]+1):
    if bisect.bisect_left(d,i)==n-bisect.bisect_left(d,i):
        ans+=1

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

import copy

n = int(input())

lis = []
for _ in range(n):
    lis.append(int(input()))
    
m = max(lis)

for i in range(n):
    if lis[i] == m:
        tlis = copy.deepcopy(lis)
        tlis.remove(lis[i])
        print(max(tlis))
    else:
        print(m)

### FIXED CODE ###

import copy

n = int(input())

lis = []
for _ in range(n):
    lis.append(int(input()))
    
slis = sorted(copy.deepcopy(lis), reverse=True)
    
m = max(lis)
s = sorted(slis, reverse=True)
s.remove(m)
sm = max(s)


for i in range(n):
    if lis[i] != m:
        print(m)
    else:
        print(sm)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = []
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if L[j] < L[k]+L[i] and L[k] < L[i]+L[j]:
                ans.append(0)
print(len(ans))

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        cnt += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

print(cnt)
### BUGGY CODE ###

import itertools
n, m = map(int, input().split())
x, y, z = [0]*n, [0]*n, [0]*n
for i in range(n):
  x[i], y[i], z[i] = map(int, input().split())
output = 0
for i in list(itertools.combinations(range(n), m)):
  sum_x = abs(sum([x[s] for s in i]))
  sum_y = abs(sum([y[s] for s in i]))
  sum_z = abs(sum([z[s] for s in i]))
  if output <= abs(sum_x)+abs(sum_y)+abs(sum_z):
    output = abs(sum_x)+abs(sum_y)+abs(sum_z)
print(output)

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  ppp = []
  ppm = []
  pmp = []
  pmm = []
  mpp = []
  mpm = []
  mmp = []
  mmm = []
  for _ in range(N):
    x, y, z = map(int, input().split())
    ppp.append(x+y+z)
    ppm.append(x+y-z)
    pmp.append(x-y+z)
    pmm.append(x-y-z)
    mpp.append(-x+y+z)
    mpm.append(-x+y-z)
    mmp.append(-x-y+z)
    mmm.append(-x-y-z)
  ppp = sorted(ppp, key=lambda x:-x)
  ppm = sorted(ppm, key=lambda x:-x)
  pmp = sorted(pmp, key=lambda x:-x)
  pmm = sorted(pmm, key=lambda x:-x)
  mpp = sorted(mpp, key=lambda x:-x)
  mpm = sorted(mpm, key=lambda x:-x)
  mmp = sorted(mmp, key=lambda x:-x)
  mmm = sorted(mmm, key=lambda x:-x)

  ans = max(sum(ppp[:M]), sum(ppm[:M]), sum(pmp[:M]), sum(pmm[:M]),
            sum(mpp[:M]), sum(mpm[:M]), sum(mmp[:M]), sum(mmm[:M]))
  print(ans)


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

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

A.sort()
m = 2 ** 31
used = set()
ans = 0

def search(ok, ng, n):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if A[mid] < n or (A[mid] == n and mid in used):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    m //= 2
    for j in range(n):
        if j in used or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                a += 1
                if a >= n or not A[a] == A[j]:
                    continue
            used.add(a)
            used.add(j)
            ans += 1

ans2 = 0
used = set()
m = 1

for i in range(31):
    m *= 2
    for j in range(n):
        if j in used or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                a += 1
                if a >= n or not A[a] == A[j]:
                    continue
            used.add(a)
            used.add(j)
            ans2 += 1

print(max(ans, ans2))

### FIXED CODE ###

from collections import Counter

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

A.sort(reverse=True)
C = Counter(A)
m = 1 << 30
ans = 0

for a in A:
    if C[a] <= 0:
        continue
    C[a] -= 1
    while m > a * 2:
        m >>= 1
    v = m - a
    if v in C and C[v] > 0:
        C[v] -= 1
        ans += 1

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

from fractions import gcd

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

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

if N == 1:
    res = 1
else:
    l = lcm(A[0], A[1])
    for i in range(2, N):
        l = lcm(l, A[i])

    for i in range(N):
        res += l//A[i]

print(res % 1000000007)

### FIXED CODE ###

from fractions import gcd

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

l = A[0]
for i in range(1, N):
    l = l * A[i] // gcd(l, A[i])

for a in A:
    res += l//a

print(res % 1000000007)
### BUGGY CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(20):
        if i + six ** p <= N:
            dp[i + six ** p] = min(dp[i + six ** p], dp[i] + 1)
        if i + nine ** p <= N:
            dp[i + nine ** p] = min(dp[i + nine ** p], dp[i] + 1)

print(dp[N])

### FIXED CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(10):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= 6
        nine *= 9

print(dp[N])
### BUGGY CODE ###

import heapq
N,M = map(int, input().split())
E = [[] for _ in range(N)]
memo = [0]*N
for _ in range(N+M-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    memo[b-1] = 1

root = memo.index(0)
rnk = [0]*N
par = [-1]*N

h = [-root]
while h:
    temp = heapq.heappop(h)
    temp *= -1
    u = temp%N
    r = temp//N
    for v in E[u]:
        if rnk[v] > r+1:
            continue
        rnk[v] = r+1
        par[v] = u
        heapq.heappush(h, -(r+1)*N-v)

for p in par:
    print(p+1)

### FIXED CODE ###

N,M = map(int, input().split())
edge = [[] for _ in range(N)]
deg = [0]*N
parent = [[] for _ in range(N)]
for _ in range(N-1+M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
    deg[y-1] += 1
    parent[y-1].append(x-1)
    
from collections import deque
res = list(v for v in range(N) if deg[v] == 0)
q = deque(res)
while q:
    v = q.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t] == 0:
            q.append(t)
            res.append(t)
    
res.reverse()
f = [0]*N
for i in range(N):
    f[res[i]] = i
    
ans = [0]*N
for i in range(N):
    if parent[i]:
        temp = parent[i][0]
        for p in parent[i]:
            if f[temp] > f[p]:
                temp = p
        ans[i] = temp+1
        
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import re
s=input()
m=0
s1 = re.compile(r'01|10')
l1 = re.compile(r'00000000000000000000001111111111111111111111|11111111111111111111110000000000000000000000')
for i in range(len(s)//2):
  dst = re.sub(s1, "", s)
  dst = re.sub(l1, "", dst)
  if dst == s:
    break
  m += len(s) - len(dst)
  s=dst
print(m)

### FIXED CODE ###

s=input();print(min(s.count("0"), s.count("1"))*2)
### BUGGY CODE ###

n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(1,n):
  for j in range(i+1,n+1):
    d_o=j-i
    if i<=x and i<=y and j<=x and j<=y:
      d_d=10**9
    elif i>=x and i>=y and j>=x and j>=y:
      d_d=10**9
    elif i<=x and i<=y and j>=x and j>=y:
      d_d=x-i+1+j-y
    elif i<=x and i<=y and x<=j<=y:
      d_d=x-i+1+(y-j)
    elif x<=i<=y and j>=x and j>=y:
      d_d=i-x+1+j-y
    elif x<=i<=y and x<=j<=y:
      d_d=i-x+1+y-j
    else:
      print("###")
    tmp=min(d_o,d_d)
    ans[tmp-1]+=1

for i in ans:
  print(i)

### FIXED CODE ###

n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(1,n):
  for j in range(i+1,n+1):
    d_o=j-i
    if i<=x and i<=y and j<=x and j<=y:
      d_d=10**4
    elif i>=x and i>=y and j>=x and j>=y:
      d_d=10**4
    elif i<=x and i<=y and j>=x and j>=y:
      d_d=x-i+1+j-y
    elif i<=x and i<=y and x<=j<=y:
      d_d=x-i+1+(y-j)
    elif x<=i<=y and j>=x and j>=y:
      d_d=i-x+1+j-y
    elif x<=i<=y and x<=j<=y:
      d_d=i-x+1+y-j
    else:
      print("###")
    tmp=min(d_o,d_d)
    ans[tmp-1]+=1

for i in ans:
  print(i)
### BUGGY CODE ###

n,m = map(int,input().split())

mod =pow(10,9) + 7
from operator import mul
from functools import reduce

def factrial(n):
    over = reduce(mul, range(n, 0, -1))
    return over

if n==m:
    value = (factrial(n) * factrial(m) * 2 )%mod

    print(value)

elif abs(n-m)>2:
    print(0)
else:
    ans = (factrial(n) * factrial(m))%mod

    print(ans)

### FIXED CODE ###

n,m = map(int,input().split())

from math import factorial
mod =(10**9) + 7
# v_n = 1
# for i in range(1,n+1):
#     v_n*= i%mod
# v_m = 1
# for j in range(1,m+1):
#     v_m*= j%mod

v_n = factorial(n)
v_m = factorial(m)
if n==m:
    value = (v_n *v_m * 2)%mod
    print(value)

elif abs(n-m)>=2:
    print(0)

else:
    ans = (v_n * v_m)%mod
    print(ans)
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))

d = dict()
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

for k in range(0, N):
    c = 0
    ak = A[k]
    for key, v in d.items():
        if key == ak:
            c += (v-1)*(v-2)//2
        else:
            c += v*(v-1)//2
    print(c)

### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))

d = dict()
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

counts = 0
for k, v in d.items():
    counts += v*(v-1)//2

for k in range(0, N):
    ak = A[k]
    print(counts - d[ak] + 1)
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
d = []
count = 0
t = [0] * n
for _ in range(n):
    s = input()
    dic = defaultdict(int)
    for c in s:
        dic[c] += 1
    for i in range(len(d)):
        if all(dic[key] == d[i][key] for key in dic):
            if t[i] != 0:
                count += t[i] + 1
                t[i] += 1
                break
            else:
                count += 1
                t[i] += 1
    d.append(dic)


print(count)


### FIXED CODE ###

import collections

n = int(input())
S = []
count = 0
for _ in range(n):
    S.append(''.join(sorted(list(input()))))

for i, v in collections.Counter(S).items():
    for i in range(1, v):
        count += i

print(count)
### BUGGY CODE ###

# n, m, l = map(int, input().split())

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

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

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

if 1 not in A:
    print(-1)
    exit()

tempA = A.copy()
i = 1
while i in set(tempA):
    k = tempA.index(i) + 1
    tempA = tempA[k:]
    i += 1

print(N-(i-1))


### FIXED CODE ###

# n, m, l = map(int, input().split())

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

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

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

n = 1
ans = 0
for i in A:
    if i == n:
        n += 1
    else:
        ans += 1
if n == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,w=map(int,input().split())
dp=[0 for i in range(w+1)]
dp1=dp.copy()
for i in range(1,n+1):

	
    
	a,b=map(int,input().split())
	
	for j in range(1,w+1):
		dp1[j]=dp[j]
		if(a<=j):
			dp1[j]=max(dp1[j],dp[j-a]+b)
	
	dp=dp1.copy()
print(dp[w])





### FIXED CODE ###

n,w=map(int,input().split())
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(w):
	dp[0][i]=0
for i in range(n):
	dp[i][0]=0
l=[]
for k in range(n):
	l.append(list(map(int,input().split())))

for i in range(1,n+1):
	for j in range(1,w+1):
		dp[i][j]=dp[i-1][j]
		if(l[i-1][0]<=j):
			dp[i][j]=max(dp[i-1][j-l[i-1][0]]+l[i-1][1],dp[i][j])
print(dp[n][w])
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
# from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

### FIXED CODE ###

import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)