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

from collections import deque
import sys
sys.setrecursionlimit(10**6)

def bfs1(c):
    visited[c]=1
    q=deque([c])
    while len(q)>0:
        p=q.popleft()
        for i in v[p]:
            if visited[i]==0:
                q.append(i)
                visited[i]=1
                d[c][i]=d[c][p]+1

def bfs2(c1,c2):
    visited[c2]=1
    bfs1(c1)
    bfs1(c2)

n,k=map(int,raw_input().split())
d=[[0]*n for _ in xrange(n)]
v=[[] for _ in xrange(n)]
e=[]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    e.append([a,b])
if k%2==0:
    min_del=1000000
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        bfs1(i)
        for j in xrange(n):
            if d[i][j]>k/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=1000000
    for i,j in e:
        cnt=0
        visited=[0]*n
        d=[[0]*n for _ in xrange(n)]
        bfs2(i,j)
        for l in xrange(n):
            if d[i][l]>(k-1)/2 or d[j][l]>(k-1)/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)

def bfs1(c):
    visited[c]=1
    q=deque([c])
    while len(q)>0:
        p=q.popleft()
        for i in v[p]:
            if visited[i]==0:
                q.append(i)
                visited[i]=1
                d[c][i]=d[c][p]+1

def bfs2(c1,c2):
    visited[c2]=1
    bfs1(c1)
    bfs1(c2)

n,k=map(int,raw_input().split())
d=[[0]*n for _ in xrange(n)]
v=[[] for _ in xrange(n)]
e=[]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    e.append([a,b])
if k%2==0:
    min_del=2005
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        bfs1(i)
        for j in xrange(n):
            if d[i][j]>k/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=2005
    for i,j in e:
        cnt=0
        visited=[0]*n
        bfs2(i,j)
        for l in xrange(n):
            if d[i][l]>(k-1)/2 or d[j][l]>(k-1)/2:
                cnt+=1
        min_del=min(min_del,cnt)
        d[i]=[0]*n
        d[j]=[0]*n
    print(min_del)
### BUGGY CODE ###

#!python3

import itertools

import numpy as np


INF = 10 ** 5

# input
H, W, K = list(map(int, input().split()))
S = [input() for _ in range(H)]


def solve(w, l):
    n = len(l)
    x = np.zeros((n + 1, W), dtype=int)
    if n == 0:
        x[0] = w[-1]
    else:
        x[0] = w[l[0]]
        for i in range(1, n):
            x[i] = w[l[i]] - w[l[i-1]]
        x[-1] = w[-1] - w[l[-1]]
    if np.any(x > K):
        return INF
    ans = 0
    dp = x[:, 0]
    for i in range(1, W):
        dp += x[:, i]
        if np.any(dp > K):
            ans += 1
            dp = x[:, i]
    return ans


def main():
    w = np.array([[int(S[i][j]) for j in range(W)] for i in range(H)])
    w = np.cumsum(w, axis=0)

    ans = INF
    num_list = [i for i in range(H)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

import itertools


INF = 10 ** 5

# input
H, W, K = list(map(int, input().split()))
S = [[int(e) for e in input()] for _ in range(H)]


def solve(w, l):
    n = len(l) + 1
    ans = 0
    if n == 1:
        dp = 0
        for j in range(W):
            x = w[-1][j]
            if x > K:
                return INF
            dp += x
            if dp > K:
                ans += 1
                dp = x
    else:
        dp = [0] * n
        for j in range(W):
            x = [0] * n
            b = False
            for i in range(n):
                if i == 0:
                    x[i] = w[l[i]][j]
                elif i == n - 1:
                    x[i] = w[-1][j] - w[l[-1]][j]
                else:
                    x[i] = w[l[i]][j] - w[l[i-1]][j]
                if x[i] > K:
                    return INF
                dp[i] += x[i]
                if dp[i] > K:
                    b = True
            if b:
                dp = x
                ans += 1
    return ans


def main():
    w = [S[0]]
    for i in range(1, H):
        w.append([w[i-1][j] + S[i][j] for j in range(W)])

    ans = INF
    num_list = [i for i in range(H - 1)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


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

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[set() for _ in range(w)] for _ in range(h)]
    dp[0][0].add(diff[0][0])

    from collections import deque
    que = deque()
    que.append((1, 0))
    que.append((0, 1))

    seen = [[False] * w for _ in range(h)]

    while que:
        row, col = que.popleft()

        if row + 1 < h:
            if not seen[row + 1][col]:
                seen[row + 1][col] = True
                que.append((row + 1, col))
        if col + 1 < w:
            if not seen[row][col + 1]:
                seen[row][col + 1] = True
                que.append((row, col + 1))

        curset = set()
        prevset = set()
        curdiff = diff[row][col]

        if row - 1 >= 0:
            prevset |= dp[row - 1][col]
        if col - 1 >= 0:
            prevset |= dp[row][col - 1]

        for num in prevset:
            curset.add(num + curdiff)
            curset.add(abs(num - curdiff))
        dp[row][col] |= curset

    cand = list(dp[h - 1][w - 1])

    print(min(cand))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[1 << (80 * 160 + 1) for _ in range(w)] for _ in range(h)]
    dp[0][0] |= 1 << diff[0][0]

    from itertools import product

    for row, col in product(range(h), range(w)):
        diff_cur = diff[row][col]
        prevset = 0

        if row - 1 >= 0:
            prevset |= dp[row - 1][col]
        if col - 1 >= 0:
            prevset |= dp[row][col - 1]

        dp[row][col] |= (prevset << diff_cur)
        dp[row][col] |= (prevset >> diff_cur)
        temp = 0
        for i in range(diff_cur):
            if prevset >> i & 1:
                temp += (1 << diff_cur - i)
        dp[row][col] |= temp

    for i in range(12801):
        if dp[h - 1][w - 1] >> i & 1:
            print(i)
            sys.exit()


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

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

j=n
for i in range(n):
	k=s[:i].count("W")+s[(i+1):].count("E")
	if j>k:
		j=k
print(j)


### FIXED CODE ###

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

j=s[1:].count("E")
t=[j]
for i in range(n-1):
	t.append(t[i]+s[i].count("W")-s[i+1].count("E"))
	if j>t[i+1]:
		j=t[i+1]
print(j)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

n, q = map(int, input().split())
edges = [[] for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p - 1] += x

ans = [0 for _ in range(n)]
visit = [False for _ in range(n)]

def rec(pos, val):
    val += cnt[pos]
    ans[pos] = val
    for to in edges[pos]:
        if not visit[to]:
            visit[to] = True
            rec(to, val)

visit[0] = True
rec(0, 0)
for x in ans[:-1]:
    print(x, end=' ')
print(ans[-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

n, q = map(int, input().split())
edges = [[] for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p - 1] += x

ans = [0 for _ in range(n)]

visit = [False for _ in range(n)]
visit[0] = True

stack = []
stack.append((0, 0))

while stack:
    pos, val = stack.pop(-1)
    val += cnt[pos]
    ans[pos] = val
    for to in edges[pos]:
        if not visit[to]:
            visit[to] = True
            stack.append((to, val))

for x in ans[:-1]:
    print(x, end=' ')
print(ans[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
z = a[0]
t = 1

while t != 0:
    t = 0
    for i in range(1,n):
        if z % a[i] != 0:
            t = 1
    if t == 1:
        z += a[0]

y = 0
for i in range(n):
    y += z // a[i]

print(z / y)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
t = 0

for i in range(n):
    t += 1 / a[i]

print(1 / t)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
  acp = a.copy()
  acp[i] = 0
  acp.sort()
  print(acp[-1])

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

sorted_a = a.copy()
sorted_a.sort()
if sorted_a[-1] == sorted_a[-2]:
  for i in range(n):
    print(sorted_a[-1])
else:
  for i in range(n):
    if a[i] == sorted_a[-1]:
      print(sorted_a[-2])
    else:
      print(sorted_a[-1])
### BUGGY CODE ###

X = int(input())
N = X//100
def get_change(pay, N):
    if N >= 0:
        for n in range(6):
            if pay%(100+n) == 0:
                print(1)
                exit(0)
            if pay > 100+n:
                get_change(pay-100-n, N-1)
    return 2
res = get_change(X, N)
if res == 2:
    print(0)


### FIXED CODE ###

X = int(input())
N = X//100
pay = X-N*100
if pay/5 > N:
    print(0)
else:
    print(1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 親の番号 根なら要素数(負の数)

    def find(self, x):
        """木の根を求める"""
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """xとyの属する集合を併合"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

l = [[False] * N for _ in range(N)]
pena = [0] * N

uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    l[A][B] = True
    l[B][A] = True
    pena[A] += 1
    pena[B] += 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if not l[C][D] and uf.same(C, D):
        pena[C] += 1
        pena[D] += 1

ans = []

for i in range(N):
    ans.append(uf.size(i) - pena[i] - 1)

print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 親の番号 根なら要素数(負の数)

    def find(self, x):
        """木の根を求める"""
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """xとyの属する集合を併合"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

uf = UnionFind(N)
ans = [0] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    ans[A] -= 1
    ans[B] -= 1

for i in range(N):
    ans[i] += uf.size(i) - 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        ans[C] -= 1
        ans[D] -= 1

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

from bisect import insort_left

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

d = []

for i in range(m):
    b,c = map(int,input().split())
    
    for j in range(b):
        d.append(c)        

d.sort()
d.reverse()

#print(a)
#print(d)

for i in range(n):
    if i >= len(d):
        break

    if a[i] < d[i]:
        a[i] = d[i]
    else:
        break

#print(a)

sum = 0
for v in a:
    sum += v

print(sum)

### FIXED CODE ###

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

d = []

bc = []
for i in range(m):
    b,c = map(int,input().split())
    bc.append([b,c])

bc = sorted(bc,key=lambda x:x[1],reverse=True)

for elm in bc:
    for i in range(elm[0]):
        d.append(elm[1])
        if len(d) >= n:
            break
    if len(d) >= n:
        break

d.sort()
d.reverse()

#print(a)
#print(d)

sum = 0
ln = len(d)
for i in range(n):
    if i < ln:
        if a[i] < d[i]:
            sum += d[i]
        else:
            sum += a[i]
    else:
        sum += a[i]

print(sum)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


H, W = map(int, input().split())

A = [list(map(lambda x: x == "#", input())) for i in range(H)]

lu = [[float("inf") for i in range(W + 2)] for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


H, W = map(int, input().split())

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20] * (W+2) for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = []
[dist.extend(l[1:-1]) for l in lu[1:-1]]
print(max(dist))
### BUGGY CODE ###

def EV(num):
    sum=0
    for j in range(1,num+1):
        sum+=j
    return sum/num

if __name__=="__main__":
    n,k=map(int,input().split())
    p=list(map(int,input().split()))

    exp={}

    ans=0
    cnt=0

    for j in range(0,n-k+1):

        tmp=0
        for i in range(k):
            if p[i+cnt] not in exp:
                exp[p[i+cnt]] = EV(p[i+cnt])
            tmp+=exp[p[i+cnt]]
        if ans < tmp:
            ans=tmp
        cnt += 1

    print(ans)

### FIXED CODE ###

from itertools import accumulate

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

exp={}
cum=[]

ans=0
cnt=0
for i in range(1,1001):
    sum=0
    for j in range(1,i+1):
        sum+=j
    exp[i]=sum/i

for i in p:
    cum.append(exp[i])

cumsum=list(accumulate(cum))
cumsum.insert(0,0)

for i in range(n-k+1):
    tmp = cumsum[i+k] - cumsum[i]
    if ans <= tmp:
        ans = tmp

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

import sys
readline = sys.stdin.readline
N, M, Q = map(int, readline().split())
X = [[0] * N for _ in range(N)]
for _ in range(M):
    l, r = map(int, readline().split())
    X[l-1][r-1] += 1

S = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        S[i+1][j+1] = S[i+1][j] + X[i][j]

for _ in range(Q):
    p, q = map(int, readline().split())
    p -= 1
    q -= 1
    ans = sum(S[i][q+1] - S[i][p] for i in range(p + 1, q + 2))
    print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
N, M, Q = map(int, readline().split())
X = [[0] * N for _ in range(N)]
for _ in range(M):
    l, r = map(int, readline().split())
    X[l-1][r-1] += 1

S = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        S[i+1][j+1] = S[i+1][j] + X[i][j]

for _ in range(Q):
    p, q = map(int, readline().split())
    p -= 1
    q -= 1
    ans = sum(S[i][q+1] - S[i][p] for i in range(p + 1, q + 2))
    print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
a = 0

for i in range(q):
    t = input().split()
    if t[0] == '2':
        if t[1] == '1' and a == 0 or t[1] == '2' and a == 1:
            s = t[2] + s
        else:
            s += t[2]

    else:
        if a == 1:
            a = 0
        else:
            a = 1
        
if a == 1:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###

s = input()
q = int(input())
Flag = False
right=''
left=''

for i in range(q):
    t = input()
    if t[0] == '1':
        Flag = not Flag
    else:
        _, f, c = t.split()
        if Flag == False and f == '2' or Flag == True and f == '1':
            right += c
        else:
            left += c

ans = left[::-1] + s + right
print(ans if not Flag else ans[::-1])
### BUGGY CODE ###

from operator import mul
from functools import reduce

n, a, b = map(int, input().split())

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n-r, -1))
    under = reduce(mul, range(1, r+1))
    return over // under

mod = 10**9+7

ans = (pow(2, n, mod) -1 - cmb(n, a) % mod - cmb(n, b) % mod) % mod

print(ans)

### FIXED CODE ###

def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

ans = (pow(2, n, mod) -1 - modComb(n, a, mod)
       - modComb(n, b, mod)) % mod

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

s=input()
K=int(input())
 
ans=[]
ans.append(s)
 
 
for i in range(len(s)-1):
 for j in range(i+2):
  cut_s=s[j:j+len(s)-i-1]
  if cut_s not in ans:
   ans.append(cut_s)
   ans.sort()
  if len(ans)>K:
    ans.pop()
 
answer=ans[K-1]
print(answer)

### FIXED CODE ###

s=input()
K=int(input())
 
ans=[]
ans.append(s)
 
 
for i in range(len(s)):
 for j in range(len(s)-i):
  cut_s=s[i:i+j+1]
  ans.append(cut_s)
  ans=sorted(set(ans))
  if len(ans)>K:
   if cut_s==ans[K]:
     ans.pop()
     break;
   ans.pop()
 
answer=ans[K-1]
print(answer)
### BUGGY CODE ###

import io
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)
HOGE = 10 ** 9 + 7


def IN_S():
  return input()


def IN_I():
  return int(input())


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


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
2000 3
'''


def MAIN():
  # T_IN()
  A()


def A():
  x = IN_L_I()
  n = x[0]
  k = x[1]

  for i in range(1, k + 1):
    blue = f(k, i)

    red = 0
    red += f(n - k, i - 1)
    red += f(n - k, i)
    red += f(n - k, i)
    red += f(n - k, i + 1)

    res = int((blue * red) % HOGE)
    print(res)
  return None


def f(x: int, y: int):
  if x < y:
    return 0
  if x == y == 0:
    return 1
  if y < 1:
    return 0
  return f2(x - y, y)


def f2(x: int, y: int):
  return c(x + y - 1, y - 1)


def c(a: int, b: int):
  return pascal(a, b)


@lru_cache(maxsize=None)
def pascal(x, y):
  if x == 0 or y == 0 or x == y:
    return 1
  else:
    return (pascal(x - 1, y - 1) + pascal(x - 1, y)) % HOGE


MAIN()


### FIXED CODE ###

import io
import sys

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def IN_S():
  return input()


def IN_I():
  return int(input())


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


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
2000 3
'''


def MAIN():
  # T_IN()
  cmb_init(MOD)
  A()


def A():
  x = IN_L_I()
  n = x[0]
  k = x[1]

  res = []
  for i in range(1, k + 1):
    blue = f(k, i)

    # red = 0
    # red += f(n - k, i - 1)
    # red += f(n - k, i)
    # red += f(n - k, i)
    # red += f(n - k, i + 1)
    red = f2(n - k - (i - 1), i + 1)

    res.append((blue * red) % MOD)

  [print(i) for i in res]
  return None


def f(x: int, y: int):
  if x < y:
    return 0
  if x == y == 0:
    return 1
  if y < 1:
    return 0
  return f2(x - y, y)


def f2(x: int, y: int):
  return c(x + y - 1, y - 1)


def c(a: int, b: int):
  return cmb(a, b, MOD)


def track(func):
  def tracked(*args, **kwargs):
    result = func(*args, **kwargs)
    name = func.__name__
    arg_str = ",".join(repr(arg) for arg in args)
    print("%s(%s) -> %r" % (name, arg_str, result))
    return result

  return tracked


### CMB ###############################
def cmb(n, r, mod):
  if (r < 0 or r > n):
    return 0
  r = min(r, n - r)
  return g1[n] * g2[r] * g2[n - r] % mod


def cmb_init(mod):
  for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


N = 10 ** 4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

### CMB ###############################


MAIN()
### BUGGY CODE ###

n = int(input())
c = list(map(int, input().split()))
ln = []
if c.count(1) == 0:
    print(-1)
else:
    c2 = c
    for i in range (1, max(c)+1):
        if i in c2 :
            s = c2.index(i)
            ln.append(i)
            del c2[:s + 1]
            if len(c2) == 1 and  i + 1 in c2:
                    ln.append(i + 1)
        else:
            break
    print(n - max(ln))   

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
now = 1
brok = 0
for i in range (n):
    if(A[i] != now):
        brok += 1
    else:
        now += 1
if(now == 1):
    print(-1)
else:
    print(brok)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
    print(len([j for j in A if j == i]))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
import collections
new_A=collections.Counter(A)
for i in B:
    print(new_A[i])
### BUGGY CODE ###

a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if v<w:
  print("NO")
  exit()
diff=abs(a-b)
for _ in range(t):
  diff=diff-v+w
  if diff<=0:
    print("YES")
    exit()
print("NO")

### FIXED CODE ###

a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if v<w:
  print("NO")
  exit()
diff=abs(a-b)
for _ in range(t):
  diff=diff-v+w
  if diff<=0:
    print("YES")
    exit()
print("NO")