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

import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

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

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E.get(u1,[]):
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = dict()
p2 = dict()
for i in range(m):
  p[u[i]-1]=p.get(u[i]-1,[])+[(v[i]-1,a[i])]
  p[v[i]-1]=p.get(v[i]-1,[])+[(u[i]-1,a[i])]
  p2[u[i]-1]=p2.get(u[i]-1,[])+[(v[i]-1,b[i])]
  p2[v[i]-1]=p2.get(v[i]-1,[])+[(u[i]-1,b[i])]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

for i in ans[::-1]:
  print(10**15-i)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

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

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

for i in ans[::-1]:
  print(10**15-i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def resolve():
    N, Q = map(int, input().split())

    AB = [[int(x) for x in input().split()] for _ in range(N - 1)]
    PX = [[int(x) for x in input().split()] for _ in range(Q)]

    graph = [[] for _ in range(N + 1)]
    for a, b in AB:
        graph[a].append(b)
        graph[b].append(a)

    value = [0] * (N + 1)
    for p, x in PX:
        value[p] += x

    def dfs(v, parent):
        for i in graph[v]:
            if i == parent:
                continue
            value[i] += value[v]
            dfs(i, v)

    dfs(1, 0)
    ans = ' '.join(map(str, value[1:]))
    return print(ans)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split())

AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)

value = [0] * (N+1)
for p, x in PX:
  value[p] += x

def dfs(v, parent):  
  for i in graph[v]:
    if i == parent:
      continue
    value[i] += value[v]
    dfs(i, v)

dfs(1, 0)    
ans = ' '.join(map(str, value[1:]))
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
c=0
for i in range(k+1):
  for i2 in range(k+1):
    for i3 in range(k+1):
      if i+i2+i3==s:
        c+=1
print(c)

### FIXED CODE ###

k,s=map(int,input().split())
c=0
for i in range(k+1):
  for i2 in range(k+1):
      if i+i2>s:
        break
      elif s-(i+i2) <=k: 
        c+=1
print(c)
### BUGGY CODE ###

def combinations_with_replacement(elements, N):
    for element in elements:
        if N == 1:
            yield [element]
        else:
            for combination in combinations_with_replacement(elements, N-1):
                if element >= combination[-1]:
                    yield combination + [element]


N, M, Q = map(int, input().split())
a = [None for _ in range(Q)]
b = [None for _ in range(Q)]
c = [None for _ in range(Q)]
d = [None for _ in range(Q)]
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

ans = 0
elements = list(range(1, M+1))
for combination in combinations_with_replacement(elements, N):
    score = 0
    for i in range(Q):
        if combination[b[i]-1] - combination[a[i]-1] == c[i]:
            score += d[i]
    ans = max(score, ans)
print(ans)


### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
a = [None for _ in range(Q)]
b = [None for _ in range(Q)]
c = [None for _ in range(Q)]
d = [None for _ in range(Q)]
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

ans = 0
elements = list(range(1, M+1))
for combination in itertools.combinations_with_replacement(elements, N):
    score = 0
    for i in range(Q):
        if combination[b[i]-1] - combination[a[i]-1] == c[i]:
            score += d[i]
    ans = max(score, ans)
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/arc097/tasks/arc097_a

s = input()
k = int(input())

done = set()
for i in range(26):
    w = chr(i + ord('a'))
    for j in range(len(s)):
        if s[j] == w:
            for m in range(j, len(s)):
                t = s[j:m + 1]
                if t not in done:
                    k -= 1
                    done.add(t)
    if k < 1:
        done = list(done)
        done.sort()
        print(done[k - 1])
        import sys;sys.exit()

### FIXED CODE ###

# https://atcoder.jp/contests/arc097/tasks/arc097_a

s = input()
k = int(input())
ans = set()

for i in range(len(s)):
    for j in range(k):
        ans.add(s[i:i + j + 1])
print(sorted(list(ans))[k - 1])
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7


def count_bit_flag(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))

    memo = {i: set() for i in range(N)}
    for bit in range(1, 1 << N):
        memo[count_bit_flag(bit)-1].add(bit)

    dp = [0] * (1 << N)
    dp[0] = 1
    for i, bit_list in enumerate(memo.values()):
        for bit in bit_list:
            for j, a in enumerate(A[i]):
                if a and (bit >> j) & 1:
                    dp[bit] += dp[bit ^ (1 << j)]
                    dp[bit] %= mod
    print(dp[(1 << N) - 1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7


def count_bit_flag(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))

    memo = {i: set() for i in range(N)}
    for bit in range(1, 1 << N):
        memo[count_bit_flag(bit)-1].add(bit)

    dp = [0] * (1 << N)
    dp[0] = 1
    for i, bit_list in enumerate(memo.values()):
        for bit in bit_list:
            for j, a in enumerate(A[i]):
                if a and (bit >> j) & 1:
                    dp[bit] += dp[bit ^ (1 << j)]
                    dp[bit] %= mod
    print(dp[(1 << N) - 1])


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

import collections as cl
import sys
input = sys.stdin.readline

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
# print(S_list)
c = cl.Counter(S_list)
# print(c)

max_list = sorted([kv[0] for kv in c.items() if kv[1] == max(c.values())])
print(*max_list)

### FIXED CODE ###

import collections as cl
import sys
input = sys.stdin.readline

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
# print(S_list)
c = cl.Counter(S_list)
# print(c)
max_num = max(c.values())

max_list = sorted([kv[0] for kv in c.items() if kv[1] == max_num])
print(*max_list)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
    for j in range(max(0, i - K), i):
        dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]))
print(dp[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
    for j in range(max(0, i - K), i):
        dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]

counter = collections.Counter(s)
ans = []
for i in counter.keys():
    if counter[i] == counter.most_common()[0][1]:
        ans.append(i)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

import collections
 
n = int(input())
s = [input() for i in range(n)]
 
counter = collections.Counter(s)
most = counter.most_common()
ans = []
for i in range(len(counter.keys())):
    if most[i][1] == most[0][1]:
        ans.append(most[i][0])
    else:
        break
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())
max = 0

for x in range(1, n+1):
    tmp = math.floor((a*x) / b) - a * math.floor(x/b)
    if tmp > max:
        max = tmp

print(max)


### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = min(b-1, n)
print(math.floor((a*x)/b) - a * math.floor(x/b))
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A_B=[0]*(X*Y)
for i in range(X):
    for j in range(Y):
        A_B[i*Y+j]=A[i]+B[j]
A_B_s=sorted(A_B,reverse=True)
if len(A_B_s)>3000:
    A_B_s=A_B_s[:3000]
W=len(A_B_s)
A_B_C=[0]*(W*Z)
for i in range(W):
    for j in range(Z):
        A_B_C[Z*i+j]=A_B_s[i]+C[j]
A_B_C_s=sorted(A_B_C,reverse=True)
for i in range(K):
    print(A_B_C_s[i])

### FIXED CODE ###

import heapq
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a=sorted([-i for i in a])
b=sorted([-i for i in b])
c=sorted([-i for i in c]) # avoid reverse=True 
a_dif=[a[i+1]-a[i] for i in range(x-1)]
b_dif=[b[i+1]-b[i] for i in range(y-1)]
c_dif=[c[i+1]-c[i] for i in range(z-1)]#差分をとる

que=[(a[0]+b[0]+c[0],(0,0,0))]
heapq.heapify(que)
s=set([(0,0,0)])
while k>0:
    ans,(ia,ib,ic)=heapq.heappop(que)
    print(-ans) #because sort with - 
    k-=1
    
    if ia < x-1 and (ia+1,ib,ic) not in s:
        heapq.heappush(que,(ans+a_dif[ia],(ia+1,ib,ic)))
        s.add((ia+1,ib,ic))
    if ib < y-1 and (ia, ib+1, ic) not in s:
        heapq.heappush(que, (ans+b_dif[ib], (ia, ib+1, ic)))
        s.add((ia, ib+1, ic))
    if ic < z-1 and (ia, ib, ic+1) not in s:
        heapq.heappush(que, (ans+c_dif[ic], (ia, ib, ic+1)))
        s.add((ia, ib, ic+1))
### BUGGY CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) % MOD * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - sum(i for i in range(1, n + 1))

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)


### FIXED CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
count=0
a=[0 for i in range(n)]
for i in range(3,n):
    a[i]=(10**i)%2019
if n<4:
    print(0)
else:
    for i in reversed(range(2,n)):
        k=int(s[i-2:i+1])%2019
        h=3
        for j in reversed(range(0,i-2)):
            k=(k+a[h]*int(s[j]))%2019
            h+=1
            if k%2019==0:
                count+=1
    print(count)

### FIXED CODE ###

import math
s=input()
n=len(s)
count=0
a=[0 for i in range(2019)]
a[0]=1
k=0
b=[0 for i in range(n)]
b[0]=1
for i in range(1,n):
    b[i]=b[i-1]*10%2019
for i in reversed(range(0,n)):
    k+=(b[n-i-1])*int(s[i])%2019
    a[k%2019]+=1        
for i in range(len(a)):
    if a[i]>=2:
        count+=(a[i])*(a[i]-1)//2
print(count)
### BUGGY CODE ###

def main():
    R, G, B, N = map(int, input().split())
    R, G, B = sorted([R, G, B])
    result = 0
    for i in range(N // G + 1):
        for j in range(N // B + 1):
            if (N - G*i - B*j) // R >= 0 and (N - G*i - B*j) % R == 0:
                result += 1
    print(result)
main()

### FIXED CODE ###

def main():
    R, G, B, N = map(int, input().split())
    R, G, B = sorted([R, G, B])
    result = 0
    for i in range(N // G + 1):
        for j in range(N // B + 1):
            if (N - G*i - B*j) < 0:
                break
            elif (N - G*i - B*j) % R == 0:
                result += 1
    print(result)
main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from itertools import accumulate

    def e(dice):
        return sum([r / dice for r in range(1, dice+1)])

    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    p_cum = [0] + list(accumulate(p))

    ma = 0
    ind = 0
    for i in range(k, n+1):
        temp = p_cum[i] - p_cum[i-k]
        if ma < temp:
            ma = temp
            ind = i

    x = p[ind-k:ind]

    print(sum(e(d) for d in x))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from itertools import accumulate

    def e(dice):
        ans = 0
        for r in range(1, dice+1):
            ans += r /dice
        return ans

    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    p_cum = [0] + list(accumulate(p))

    ma = 0
    ind = 0
    for i in range(k, n+1):
        temp = p_cum[i] - p_cum[i-k]
        if ma < temp:
            ma = temp
            ind = i

    x = p[ind-k:ind]

    print(sum(e(d) for d in x))

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

N = int(input())

for i in range(1 , 10 ** 6 + 1):
  for j in range(1 , 10 ** 6 + 1):
    if i * j == N:
      I = i - 1
      J = j - 1
      break
      
print(I + J)

### FIXED CODE ###

import math

N = int(input())
n = math.sqrt(N)
ans = 10 ** 12

for i in range(1 , math.ceil(n) + 1):
  if i * (N // i) == N:
    count = (i - 1) + ((N // i) - 1)
    ans = min(ans , count)
    
print(ans)
### BUGGY CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ia = find_index_by_value(reachable_node, a)
        ib = find_index_by_value(reachable_node, b)
        if ia == -1 and ib == -1:
            reachable_node.append({a, b})
            reachable += 1
        elif ia == -1:
            ni = len(reachable_node[ib])
            reachable_node[ib].add(a)
            reachable += num_reachable(ni + 1) - num_reachable(ni)
        elif ib == -1:
            ni = len(reachable_node[ia])
            reachable_node[ia].add(b)
            reachable += num_reachable(ni + 1) - num_reachable(ni)
        else:
            if ia != ib:
                n1, n2 = len(reachable_node[ia]), len(reachable_node[ib])
                reachable_node[ia] |= reachable_node[ib]
                reachable_node.pop(ib)
                reachable += num_reachable(n1 + n2) - num_reachable(n1) - num_reachable(n2)
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())




### FIXED CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    c = []
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
        else:
            c.append(p)
            p = pp
    for i in c:
        group[i] = pp
    return pp

# find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())
### BUGGY CODE ###

arr = []

for _ in range(int(input())):
    cmd = [int(x) for x in input().split()]

    if cmd[0] == 0:
        if cmd[1]:
            arr.append(cmd[2])
        else:
            arr.insert(0, cmd[2])
    elif cmd[0] == 1:
        print(arr[cmd[1]])
    else:
        if cmd[1]:
            arr.pop()
        else:
            arr.pop(0)



### FIXED CODE ###

from collections import deque

arr = deque()

for _ in range(int(input())):
    cmd = [int(x) for x in input().split()]

    if cmd[0] == 0:
        if cmd[1]:
            arr.append(cmd[2])
        else:
            arr.appendleft(cmd[2])
    elif cmd[0] == 1:
        print(arr[cmd[1]])
    else:
        if cmd[1]:
            arr.pop()
        else:
            arr.popleft()
### BUGGY CODE ###

s = input()
q = int(input())
cou = 1
for i in range(q):
    t = list(input().split())
    #logging.debug(t)#
    if t[0] == "1":
        cou *= -1
    else:
        if t[1] == "1" and cou == 1:
            s = t[2] + s
        elif t[1] == "2" and cou == -1:
            s = t[2] + s
        else:
            s = s + t[2]
#    logging.debug("s {},cou {}".format(s,cou))

if cou == 1:
    print(''.join(s))
else:
    print(''.join(s[::-1]))

### FIXED CODE ###

s = input()
q = int(input())
cou = 1
frt = ""
bck = ""
for i in range(q):
    t = list(input().split())
    #logging.debug(t)#
    if t[0] == "1":
        cou *= -1
    else:
        if (t[1] == "1" and cou == 1)or(t[1] == "2" and cou == -1):
            frt = t[2] + frt
        else:
            bck = bck + t[2]
#    logging.debug("s {},cou {}".format(s,cou))

s = frt + s + bck
#logging.debug(s)#
if cou == 1:
    print(''.join(s))
else:
    print(''.join(s[::-1]))
### BUGGY CODE ###

(n, m), h, *r = [[*map(int, i.split())] for i in open(0)]
c = 0
for i in range(n):
    if i + 1 not in sum(r, []):
        c += 1
        continue
    l = [j * (i + 1 in j) for j in r]
    if h[i] > max(h[j-1] for j in set(sum(l, []))-{i + 1}):
        c += 1
print(c)

### FIXED CODE ###

(n, m), h, *r = [[*map(int, i.split())] for i in open(0)]
g =[] + h

for i in r:
    g[i[0]-1] *= h[i[0]-1] > h[i[1]-1]
    g[i[1]-1] *= h[i[1]-1] > h[i[0]-1]
print(len([i for i in g if i !=0]))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]
Z = [int(i) for i in input().split()]


answer = []
for i in X:
    for j in Y:
        answer.append(i+j)
answer.sort(reverse=1)

answer2 = []
for l in Z[:k]:
    for a in answer[:k]:
        answer2.append(l+a)
answer2.sort(reverse=1)

for p in answer2[:k]:
    print(p)

### FIXED CODE ###

x, y, z, k = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]
Z = [int(i) for i in input().split()]
X.sort(reverse=1)
Y.sort(reverse=1)
Z.sort(reverse=1)

answer = [i+j for i in X[:k] for j in Y[:k]]
answer.sort(reverse=1)

answer2 = [i+j for i in Z[:k] for j in answer[:k]]
answer2.sort(reverse=1)

for p in answer2[:k]:
    print(p)
### BUGGY CODE ###

N = int(input())
a_list = list(map(int, input().split()))
cnt = 0
ref_num = 1
if 1 not in a_list:
    print(-1)
    exit()
while True:
  if a_list == []:
      print(cnt)
      exit()
  for i in range(len(a_list)):
    if ref_num not in a_list:
      cnt += len(a_list)
      print(cnt)
      exit()
    elif ref_num == a_list[i]:
      red = len(a_list[:i])
      a_list = a_list[i+1:]
      cnt += red
      ref_num += 1
      break

### FIXED CODE ###

N = int(input())
a_list = list(map(int, input().split()))
cnt = 0
ref_num = 1
for i in range(N):
  if a_list[i] == ref_num:
    ref_num += 1
  else:
    cnt += 1

if ref_num == 1:
  print(-1)
else:
  print(cnt)