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

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections

    colored  = {}
    edge_map = collections.defaultdict(list)
    for e in edge:
        edge_map[e[0]].append(e[1])
        edge_map[e[1]].append(e[0])

    root = edge[0][0]
    colored[root] = k
    for i, p in enumerate(edge_map[root]):
        colored[p] = k - (i + 1)

    visit = []
    visit.extend(edge_map[root])
    while len(colored) != n:
        current = visit.pop(0)
        not_colored = [p for p in edge_map[current] if p not in colored]
        visit = not_colored + visit
        for i, p in enumerate(not_colored):
            colored[p] = k - (i + 2)

    total = 1
    for i in colored.values():
        total *= i
        if total > 1000000007:
            total %= 1000000007
    print(total)


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007

# Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a

# Ref: https://www.smartbowwow.com/2018/10/mod1097.html
def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod

#mod_pow = mod_pow1
# It's better to use built-in function for speed.
mod_pow = pow

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) # factrial[i]
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) # inverse[i]
 
total = 1

if not edge:
    print(k)
else:
    all_edge = tuple([[] for _ in range(n + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])
    all_edge = [set(v) for v in all_edge]

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD

        def dfs(current, from_):
            global total
            child = all_edge[current]
            if len(child) - 1 > 0:
                total = (total * factorial[k - 2] * inverse[k - 2 - (len(child) - 1)]) % MOD
            for c in child:
                if c != from_:
                    dfs(c, current)
        for c in all_edge[root[0]]:
            dfs(c, root[0])
        print(total)
### BUGGY CODE ###

import heapq
N,Q = map(int, input().split())

S,T,X = [],[],[]

Ev = []
for _ in range(N):
  s,t,x = map(int, input().split())
  Ev.append((s-x,True,x))
  Ev.append((t-x,False,x))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
# C++のSetはminもO(logN)で取れるが、Pythonは無理。
# setとheapqを併用すると計算量が実現できる。
h = []
closed = set()
eidx = 0
for i in range(Q):
  # dはsortedでinputされる。
  d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      heapq.heappush(h, x)
      closed.add(x)
    else:
      closed.remove(x)
      
  # heqpqの最小値がsetに含まれている間、捨て続ければ、setの要素とheapqの要素が一致する
  while h and h[0] not in closed:
    heapq.heappop(h)
    
  # assert( len(h) == len(set) )
  if h:
    print(h[0])
  else:
    print(-1)


### FIXED CODE ###

import heapq
N,Q = map(int, input().split())

S,T,X = [],[],[]

Ev = []
for _ in range(N):
  s,t,x = map(int, input().split())
  Ev.append((s-x,True,x))
  Ev.append((t-x,False,x))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
# C++のSetはminもO(logN)で取れるが、Pythonは無理。
# setとheapqを併用すると計算量が実現できる。
h = []
closed = set()
eidx = 0
for i in range(Q):
  # dはsortedでinputされる。
  d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      heapq.heappush(h, x)
      closed.add(x)
    else:
      closed.remove(x)
      
  # heqpqの最小値がsetに含まれている間、捨て続ければ、setの要素とheapqの要素が一致する
  while h and h[0] not in closed:
    heapq.heappop(h)
    
  # assert( len(h) == len(set) )
  if h:
    print(h[0])
  else:
    print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 25 18:20:35 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

#N = int(input())
N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))

dp = [i <= K for i in range(K + A[-1]+1)]
for i in range(K, -1, -1):
    for a in A:
        if dp[a+i]:
            dp[i] = False
            break

#    print(i, dp[i],A+i,dp[A+i])
#print(dp)

if dp[0]:
    ans = 'Second'
else:
    ans = 'First'
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 25 18:20:35 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

#N = int(input())
N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))

dp = np.arange(K + A[-1]+1) >= 0
for i in range(K, -1, -1):
    if np.all(dp[A+i]):
        dp[i] = False
#    print(i, dp[i],A+i,dp[A+i])
#print(dp)

if dp[0]:
    ans = 'First'
else:
    ans = 'Second'
print(ans)
### BUGGY CODE ###

from sys import stdin
def main():
  from builtins import len, max, range
  readline = stdin.readline
  s = stdin.readline()[:-1]
  t = stdin.readline()[:-1]
  dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
  for i in range(1, len(s) + 1):
    s1i = s[i - 1]
    dpi = dp[i]
    dpi1 = dp[i - 1]
    for j in range(1, len(t) + 1):
      if s1i == t[j - 1]:
        dpi[j] = max(dpi[j], dpi1[j], dpi[j - 1], dpi1[j - 1] + 1)
      else:
        dpi[j] = max(dpi[j], dpi1[j], dpi[j - 1])
  u = []
  while True:
    dpi = dp[i]
    if dpi[j] == 0:
      break
    elif dp[i - 1][j] == dpi[j]:
      i -= 1
    elif dpi[j - 1] == dpi[j]:
      j -= 1
    else:
      u.append(s[i - 1])
      i -= 1
      j -= 1
  print(''.join(u[::-1]))
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

MOD=10**9+7
import sys
import math
import random
N=int(input())
alist=list(map(int,input().split()))
#alist.sort()
random.shuffle(alist)

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)
  
lcm=1
prod=1
for i in range(N):
  lcm=lcm*alist[i]//math.gcd(lcm,alist[i])
  prod*=alist[i]
  if lcm!=prod:    
    print("setwise coprime")
    sys.exit(0)
    
print("pairwise coprime")

### FIXED CODE ###

import sys
import math
N=int(input())
alist=list(map(int,input().split()))

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)

max_a=max(alist)  
dlist=[i for i in range(max_a+1)]
for i in range(2,int(max_a**0.5)+1):
  if dlist[i]<i:
    continue
  else:
    for j in range(i**2,max_a+1,i):
      dlist[j]=i  
#print(dlist)

fact_set=set()
for i in range(N):
  ai=alist[i]
  facts=set()
  while ai>1:
    facts.add(dlist[ai])
    ai//=dlist[ai]    
  #print(facts)
  
  for f in facts:
    if f in fact_set:
      print("setwise coprime")
      sys.exit(0)
    else:
      fact_set.add(f)
else:
  print("pairwise coprime")
### BUGGY CODE ###

def euqlid(x,y):
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
if a < b:
    tmp = a
    a = b
    b = tmp
k = euqlid(a, b)
sum = 0
i = 2
while k > 1:
    flag = False
    while k % i == 0:
        k = k // i
        flag = True
    if flag:
        sum += 1
    i += 1
print(sum + 1)

### FIXED CODE ###

import math
def euqlid(x,y):
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
if a < b:
    tmp = a
    a = b
    b = tmp
k = euqlid(a, b)
sum = 0
i = 2
if k == 1:
    print(1)
    exit()
while i <= math.sqrt(k):
    flag = False
    while k % i == 0:
        k = k // i
        flag = True
    if flag:
        sum += 1
    i += 1
if i <= k:
    sum += 1
print(sum + 1)
### BUGGY CODE ###

def LCS():
 x = raw_input()
 y = raw_input()
 i, j = len(x), len(y)

 dsp = [[0 for col in xrange(j+1)] for row in xrange(i+1)]
 for i in xrange(1,i+1):
  for j in xrange(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 print dsp[-1][-1]

q = input()
for i in xrange(q):
 LCS()

### FIXED CODE ###

def LCS():
 x = raw_input()
 y = raw_input()
 a, b = len(x), len(y)
 dsp1 = [0 for i in xrange(b+1)]
 for i in xrange(a):
  dsp2 = dsp1+[]
  for j in xrange(b):
   if x[i] == y[j]:
    dsp1[j+1] = dsp2[j] + 1
   elif dsp1[j+1] < dsp1[j]:
    dsp1[j+1] = dsp1[j]
 print max(dsp1)
  
n = input()
for a in xrange(n):
    LCS()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

args = input().split()
n = int(args[0])
m = int(args[1])
ok_list = [0] * 100000
ng_dict = {}
ok_cnt = 0
ng_cnt = 0
for _ in range(m):
    target, score = input().split()
    target = int(target)
    if target in ok_list:
        continue
    else:
        if score == 'AC':
            ok_list[ok_cnt] = target
            ok_cnt += 1
        else:
            if target in ng_dict:
                ng_dict[target] += 1
            else:
                ng_dict[target] = 1

for num in ok_list:
    if num in ng_dict:
        ng_cnt += ng_dict[num]

print(ok_cnt, ng_cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

args = input().split()
n = int(args[0])
m = int(args[1])
ok = [False] * n
ng = [0] * n
for _ in range(m):
    target, score = input().split()
    target = int(target) - 1
    if score == 'AC':
        ok[target] = True
    else:
        if not ok[target]:
            ng[target] += 1

ok_cnt = 0
ng_cnt = 0
for i in range(n):
    if ok[i]:
        ok_cnt += 1
        ng_cnt += ng[i]
print(ok_cnt, ng_cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
used = [False] * m
total = 0
score = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if used[i]:
            continue
        used[i] = True
        counts[a - 1] += 1
        total += 1
        score += b
        break
    if total == m:
        break
print(score)


### FIXED CODE ###

import heapq

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

cands = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        cands[a - 1].append(-b)

heapq.heapify(cands[0])
total = 0
for i in range(m):
    if len(cands[0]) > 0:
        total -= heapq.heappop(cands[0])
    if i < m - 1:
        for c in cands[i + 1]:
            heapq.heappush(cands[0], c)

print(total)
### BUGGY CODE ###

N = int(input())
A = list(int(x) for x in input().split())
a = len(A)
sa = sorted(A)
su = 0
p = 10**9+7
for i in range(a):
        su += sa[i]*(sum(sa[i+1:])%p)%p

print(su%p)


### FIXED CODE ###

N = int(input())
A = list(int(x) for x in input().split())
B = [0]
a = len(A)
sa = sorted(A)
su = 0
p = 10**9+7

for i in range(a):
    B.append(B[i] + sa[i])

for j in range(a):
    su += sa[j]*B[j]

print(su%p)
### BUGGY CODE ###

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = []
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w])

ans = 0
while len(painted) > 0:
    to_be_painted = []
    for blackcell in painted:
        h = blackcell[0]
        w = blackcell[1]
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
                cell[nh][nw] = '#'
                to_be_painted.append([nh, nw])
    painted = to_be_painted
    if len(painted) > 0: ans += 1

print(ans)

### FIXED CODE ###

from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

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

N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)

dp=[[0 for i in range(W+10)] for j in range(N+10)]

for i in range(N):
    for j in range(W+1):
        if(j-w[i]>=0):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)

dp=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if(j-w[i]>=0):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])
### BUGGY CODE ###

A,B,Q = map(int,input().split())
Ss = []
for i in range(A):
    Ss.append(int(input()))
Ts = []
for i in range(B):
    Ts.append(int(input()))

def binary_search(search_list,target):
    left = 0
    right = len(search_list)
    while left < right:
        center = (left + right)//2
        if search_list[center] < target:
            left = center + 1
        elif search_list[center] > target:
            right = center
    index = left
    return index-1

S_to_T = []
for i in range(A):
    index = binary_search(Ts,Ss[i])
    if index+1 == B:
        right = float('inf')
    else:
        right = abs(Ss[i]-Ts[index+1])
    length = min(abs(Ss[i]-Ts[index]),right)
    S_to_T.append(length)
T_to_S = []
for i in range(B):
    index = binary_search(Ss,Ts[i])
    if index+1 == A:
        right = float('inf')
    else:
        right = abs(Ts[i]-Ss[index+1])
    length = min(abs(Ts[i]-Ss[index]),right)
    T_to_S.append(length)

for i in range(Q):
    q = int(input())
    Sindex = binary_search(Ss,q)
    S_left = abs(Ss[Sindex]-q)+S_to_T[Sindex]
    if Sindex+1 == A:
        S_right = float('inf')
    else:
        S_right = abs(Ss[Sindex+1]-q)+S_to_T[Sindex+1]
    Tindex = binary_search(Ts,q)
    T_left = abs(Ts[Tindex]-q)+T_to_S[Tindex]
    if Tindex+1 == B:
        T_right = float('inf')
    else:
        T_right = abs(Ts[Tindex+1]-q)+T_to_S[Tindex+1]
    ans = min(S_left,S_right,T_left,T_right)
    print(ans)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

from bisect import bisect_left
inf = float('inf')


N = int(input())
A = [int(input()) for _ in range(N)]

color = [A[0]]
for a in A[1:]:
    pos = bisect_left(color, a)
    if pos == 0:
        color.insert(0,a)
    else:
        color[pos-1] = a

ans = len(color)
print(ans)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
A = [int(input()) for _ in range(N)]

color = [-1]*N

ans = 0
l = N

for i in range(N):
    pos = bisect_left(color, A[i])
    if pos == l:
        ans += 1
    color[pos-1] = A[i]

ans = len([c for c in color if c != -1])
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
A = list(map(int, input().split()))
M = 10**9+7

result = 0
for itr in itertools.combinations(A,2):
    result = (result + (itr[0]*itr[1])%M)%M

print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = 10**9+7

ruisekiwa = [0]*N
wa = sum(A)%M

result = 0
for i in range(N):
    wa -= A[i]
    result = (result+(A[i]*wa)%M)%M

print(result)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

N = int(input())
g=0
for a in range(N):
    for b in range(N):
        for c in range(N):
            g = g + gcd((a+1),(b+1),(c+1))
print(g)

### FIXED CODE ###

import math

N = int(input())
g=0
for a in range(N):
    for b in range(N):
        g_1=math.gcd((a+1),(b+1))
        for c in range(N):
            g = g + math.gcd(g_1,(c+1))
print(g)
### BUGGY CODE ###

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

All_list = list(map(int, input().split()))

for _ in range(M):
    Bi, Ci = map(int, input().split())
    All_list.extend([Ci for _ in range(Bi)])
    All_list.sort(reverse=True)
    All_list = All_list[:N]


print(sum(All_list))

### FIXED CODE ###

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

A_list = list(map(int, input().split()))

All_dict = {}

for Ai in A_list:
    if Ai not in All_dict.keys():
        All_dict[Ai] = 0
    All_dict[Ai] += 1
    
for _ in range(M):
    Bi, Ci = map(int, input().split())
    if Ci not in All_dict.keys():
        All_dict[Ci] = 0
    All_dict[Ci] += Bi
counter = 0
res = 0
all_card_val = list(All_dict.keys())
all_card_val.sort(reverse=True)
for card_val in all_card_val:
    possesion = All_dict[card_val]
    if counter + possesion <= N:
       res += card_val * possesion
       counter += possesion
    else:
        res += card_val * (N - counter)
        break

print (res)
### BUGGY CODE ###

li = input().split()
A = int(li[0])
B = int(li[1])
C = int(li[2])
D = int(li[3])

lcm=C*D
#print(A, B-A+1)
ans = []

for i in range(A, B+1):
	#print(i)
	if i%C != 0 and i%D != 0:
		#print('warikirenai')
		ans.append(i)

print(len(ans))


### FIXED CODE ###

import fractions
 
A, B, C, D = map(int, input().split())

A -= 1
lcm=C*D // fractions.gcd(C, D)

ex = A - (A // C + A // D - A // lcm)
num = B - (B // C + B // D - B // lcm)


print(num-ex)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)


def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]

    def solve(i, w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            dp[i][w] = 0
        elif w - weight[i] < 0:
            dp[i][w] = solve(i + 1, w)
        else:
            dp[i][w] = max(solve(i + 1, w), solve(i + 1, w - weight[i]) + value[i])
        #dp[i][w] = ret_val
        return dp[i][w]

    solve(0, W)
    # print(dp)
    return max(dp[0])


if __name__ == "__main__":
    print(knapsack())


### FIXED CODE ###

import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

for i in range(0,N):
    w, v = goods[i,:]
    dp[i + 1, w:] = np.maximum(dp[i,w:] , dp[i,:-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1,:],dp[i,:])
print(int(dp[N,W]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, p: "List[float]"):
    # prob[i][j]はi枚まで投げてj枚表になる確率
    prob = [[0]*(N+1) for _ in range(N+1)]
    prob[0][0] = 1
    for i in range(N):
        for j in range(N+1):
            prob[i+1][j] = prob[i][j]*(1-p[i])
            if j-1 >= 0:
                prob[i+1][j] += prob[i][j-1]*p[i]
    print(sum(prob[N][N//2+1:]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, p: "List[float]"):
    # prob[i][j]はi枚まで投げてj枚表になる確率
    prob = [[0]*(N+1) for _ in range(N+1)]
    prob[0][0] = 1
    for i in range(N):
        for j in range(N+1):
            prob[i+1][j] = prob[i][j]*(1-p[i])
            if j-1 >= 0:
                prob[i+1][j] += prob[i][j-1]*p[i]
    print(sum(prob[N][N//2+1:]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)


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

n,m=map(int, input().split())
a = [int(input()) for i in range(m)]

dp = [0] * (n+1)
dp[0] = 1
if (1 in a):
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if (i in a):
        continue
    else:
        dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)

print(dp[n])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

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

def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    for m in range(k):
        B = [0 for i in range(n + 1)]
        for i in range(n):
            l = max(0, i - A[i])
            r = min(n, i + A[i] + 1)
            B[l] += 1
            if r < n:
                B[r] -= 1

        for i in range(1, n):
            B[i] += B[i - 1]

        if A == B:
            break
        A = B[:n]

    for a in A:
        print(a, end=" ")

resolve()

### FIXED CODE ###

from numba import jit
import numpy as np

@jit
def resolve():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    for m in range(k):
        B = np.zeros(n + 1, dtype=np.int64)
        for i in range(n):
            l = max(0, i - A[i])
            r = min(n, i + A[i] + 1)
            B[l] += 1
            if r < n:
                B[r] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == n):
            break

    for a in A:
        print(a, end=" ")

resolve()
### BUGGY CODE ###

zettaiTLE = int(input())
M = [zettaiTLE]                
cnt = 0
while True:
  if M[0] == 1:
    del M[0]
    if len(M) == 0:
      cnt += 1
      print(cnt)
      exit()
  else :
    tekito = M[0]
    del M[0]
    for i in range(2):
      M.append(tekito // 2)
  cnt += 1

### FIXED CODE ###

H = int(input())
m = 1
cnt = 0
if H == 1:
  print(1)
  exit()
while True:
  if H < m:
    print(m  - 1)
    exit()
  m *= 2
  cnt += 1
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    check = P[:i+1]
    if min(check) == check[-1]:
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
check = 10**9 + 7

for i in range(N):
    if check > P[i]:
        ans += 1
        check = P[i]

print(ans)