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

def small(a, b):
    if a > b:
        return b
    else:
        return a


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                dp[i_j] = small(dp[i_j], dp[i] + abs(h[i] - h[i_j]))
    print(dp[-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    Fermatの小定理より(Nが素数のときしか使えない)
    aの逆元 ax = 1 (mod N)を満たすx = a^(N-2) mod Nを返す。
    O(log N)
    """

    def bpm(x, y, N):
        """
         Bisection power method : 二分累乗法
         O(log y)でx^(y) mod N を求める。
        """
        ans = 1
        x %= MOD
        digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
        for i in range(digit):
            if (y >> i) & 1 == 1:
                ans *= x
                ans %= MOD
            x **= 2
            x %= MOD
        return ans

    return bpm(a, N - 2, N)


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)


### FIXED CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = fractions.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)
### BUGGY CODE ###

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


floor_num=[]
for x in range(N+1):
    if x>=B:
        break
    floor_num.append(int(A*x/B)-A*int(x/B))

print(max(floor_num))

### FIXED CODE ###

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


floor_num=[]

if N >=B:
    floor_num.append(int(A*(B-1)/B))
else:  

        floor_num.append(int(A*N/B))


print(max(floor_num))
### BUGGY CODE ###

N = int(input())
s = ['']*N

for i in range(N):
  str = input()
  s[i] = ''.join(sorted(str))

s.sort()
ans = 0
for i in range(N):
  ans += s[i+1:].count(s[i])
  
print(ans)
  
  

### FIXED CODE ###

N = int(input())
s = ['']*N
 
for i in range(N):
	str = input()
	s[i] = ''.join(sorted(str))
 
s.sort()
ans = 0

#for i in range(N):
i = 0
while (i < N):
	current = s[i]
	same = 1
	while(i < N-1):
		if(s[i+1] == current):
			i += 1
			same += 1
		else:
			break

	ans += same * (same - 1)//2
	#print(i, same, ans)
	i += 1

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

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(q):
    c = 0
    while q:
        q, r = divmod(q, 2)
        c += r
    return c

ma = 5*10**5
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i%popcount(i)]+1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)

### FIXED CODE ###

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(n):
    return bin(n).count('1')

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
### BUGGY CODE ###

L, R = map(int, input().split())
mini = mod = 2019

for i in range(L, R+1):
    for j in range(i+1, R+1):
        mod = (i * j) % 2019
        mini = min(mini, mod)

print(mini)

### FIXED CODE ###

L, R = map(int, input().split())
mini = mod = 2019

for i in range(L, R+1):
    for j in range(i+1, R+1):
        mod = (i * j) % 2019
        mini = min(mini, mod)
        
        if (mini == 0):
            print(mini)
            exit()
        
print(mini)
### BUGGY CODE ###

s = [x for x in input()]

q_pos = [i if x == '?' else None for i, x in enumerate(s)]
q_pos = [x for x in q_pos if x is not None]

q_size = len(q_pos)
ans = 0
for i in range(10 ** q_size):
    r = [x for x in str(i).zfill(q_size)]
    for i_q, r_q in zip(q_pos, r):
        s[i_q] = r_q
    if (int(''.join(s)) - 5) % 13 == 0:
        ans += 1

print(ans % (10**9 + 7))

### FIXED CODE ###

MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

dp = [0] * 13
dp[0] = 1

r = [[(j-i)*4%13 for i in range(10)]for j in range(13)]

for i, x in enumerate(s):
    next_dp = [0] * 13
    if x == -1:
        next_dp = [sum(dp[i] for i in j) for j in r]
    else:
        next_dp = [dp[j[x]] for j in r]
    dp = [k % MOD for k in next_dp]

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

import sys
input = sys.stdin.readline

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]

for _ in range(N):
    s, t, c = map(int, input().split())
    lst[c][s] += 1
    lst[c][t + 1] -= 1

#番組ごとに毎分必要かどうかを判断する
for i in range(1, C + 1):
    for j in range(1, 10 ** 5 + 10): #いもす法で計算
        lst[i][j] += lst[i][j - 1]
    for j in range(1, 10 ** 5 + 10): #重なっている時 = 連続して使う時
        lst[i][j] = min(1, lst[i][j])

for j in range(1, 10 ** 5 + 10):
    for i in range(1, C + 1):
        lst[i][j] += lst[i - 1][j]

print (max(lst[-1]))


### FIXED CODE ###

# 計算量 O(NC) = O(3 * 10 ** 6)
import sys
input = sys.stdin.readline

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]

for _ in range(N):
    s, t, c = map(int, input().split())
    lst[c][s] += 1
    lst[c][t + 1] -= 1

#番組ごとに毎分必要かどうかを判断する
for i in range(1, C + 1):
    for j in range(1, 10 ** 5 + 10): #いもす法で計算
        lst[i][j] += lst[i][j - 1]
    for j in range(1, 10 ** 5 + 10): #重なっている時 = 連続して使う時
        lst[i][j] = min(1, lst[i][j])

for j in range(1, 10 ** 5 + 10):
    for i in range(1, C + 1):
        lst[i][j] += lst[i - 1][j]

print (max(lst[-1]))
### BUGGY CODE ###

from collections import Counter

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    cnt = Counter(As)

    dp = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            if j+k > N:
                break
            for i in range(N+1):
                if i+j+k > N:
                    break
                expe = 0.0
                if i > 0:
                    expe += i/N * dp[i-1][j][k]
                if j > 0:
                    expe += j/N * dp[i+1][j-1][k]
                if k > 0:
                    expe += k/N * dp[i][j+1][k-1]
                if i+j+k:
                    expe = (expe+1)*N/(i+j+k)
                dp[i][j][k] = expe

    ans = dp[cnt[1]][cnt[2]][cnt[3]]
    print(ans)


solve()


### FIXED CODE ###

from collections import Counter

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    cnt = Counter(As)

    dp = [[[0.0]*(N+1) for j in range(N+1)] for i in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            if j+k > N:
                break
            for i in range(N+1):
                if i+j+k > N:
                    break
                expe = 0.0
                if i > 0:
                    expe += i/N * dp[i-1][j][k]
                if j > 0:
                    expe += j/N * dp[i+1][j-1][k]
                if k > 0:
                    expe += k/N * dp[i][j+1][k-1]
                if i+j+k:
                    expe = (expe+1)*N/(i+j+k)
                dp[i][j][k] = expe

    ans = dp[cnt[1]][cnt[2]][cnt[3]]
    print(ans)


solve()
### BUGGY CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = []
for n in range(N):
    if n == 0:
        dp.append(0)
    else:
        l = min(n, K)
        min_num = 10 ** 10
        dp.append(min([min(abs(A[n] - A[n - k]) + dp[n - k], min_num) for k in range(1, l + 1)]))

print(dp[-1])


### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] + [None] * (N - 1)
for n, a in enumerate(A):
    if n:
        l = max(0, n - K)
        dp[n] = min(abs(a - a2) + d for a2, d in zip(A[l : n], dp[l : n]))

print(dp[-1])
### BUGGY CODE ###

import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

s = sum(A)
m = math.ceil(math.sqrt(s))

divs = []
divs2 = []
i = 1
while i < s:
	if s % i == 0:
		divs.append(i)
		divs2.append(s//i)
	i += 1
divs.reverse()
divs2 += divs

ans = 1
for n in divs2:
	B = [a % n for a in A]
	s = sum(B)
	if s % n != 0: continue
	B.sort()
	B = [b for b in B if b != 0]
	if len(B) == 0:
		ans = max(ans, n)
		break
	bsum = [0]*len(B)
	rbsum = [0]*len(B)
	bs = 0
	for i, b in enumerate(B):
		bs += b
		bsum[i] = bs
	bs = 0
	for i, b in reversed(list(enumerate(B))):
		bs += n - b
		rbsum[i] = bs
	need = float('inf')
	for i in range(len(B)-1):
		if bsum[i] == rbsum[i+1]:
			need = bsum[i]
			break
	if need <= K:
		ans = max(ans, n)
		break
print(ans)



### FIXED CODE ###

import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

s = sum(A)
m = math.ceil(math.sqrt(s))

divs = []
divs2 = []
i = 1
while i <= m:
	if s % i == 0:
		divs.append(i)
		divs2.append(s//i)
	i += 1
divs.reverse()
divs2 += divs

ans = 1
for n in divs2:
	B = [a % n for a in A]
	s = sum(B)
	if s % n != 0: continue
	B.sort()
	B = [b for b in B if b != 0]
	if len(B) == 0:
		ans = max(ans, n)
		break
	bsum = [0]*len(B)
	rbsum = [0]*len(B)
	bs = 0
	for i, b in enumerate(B):
		bs += b
		bsum[i] = bs
	bs = 0
	for i in range(len(B)-1, -1, -1):
		bs += n - B[i]
		rbsum[i] = bs
	need = float('inf')
	for i in range(len(B)-1):
		if bsum[i] == rbsum[i+1]:
			need = bsum[i]
			break
	if need <= K:
		ans = max(ans, n)
		break
print(ans)
### BUGGY CODE ###

s = input()
k = int(input())
a = set()
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        a.add(s[i:j])
print(sorted(list(a))[k - 1])


### FIXED CODE ###

s = input()
k = int(input())
a = set()
for i in range(len(s) + 1):
    for j in range(1, 6):
        a.add(s[i:i + j])
print(sorted(list(a))[k])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# N,Cを取得
n, c = map(int, input().split())

# x1, v1..xN, vNを取得
xs = []
vs = []
for _i in range(n):
    x, v = map(int, input().split())
    xs.append(x)
    vs.append(v)

r1, r2, l1, l2 = [[], [], [], []]
r_sum, l_sum = [0, 0]
for i in range(n):
    r_sum += vs[i]
    r1.append(r_sum - xs[i])
    r2.append(r_sum - 2 * xs[i])

    i_rev = n - i - 1
    l_sum += vs[i_rev]
    l1.append(l_sum - (c - xs[i_rev]))
    l2.append(l_sum - 2 * (c - xs[i_rev]))

r1_l2_max = 0
l1_r2_max = 0
for i in range(n):
    r1_max = max(r1[:i + 1])
    l2_max = max(l2[:n - i - 1] or [0])
    r1_l2_max = max(r1_l2_max, r1_max + l2_max)

    l1_max = max(l1[:i + 1])
    r2_max = max(r2[:n - i - 1] or [0])
    l1_r2_max = max(l1_r2_max, l1_max + r2_max)

total_max = max(r1_l2_max, l1_r2_max)

# 結果を出力
print("{}".format(total_max))


### FIXED CODE ###

# -*- coding: utf-8 -*-

# N,Cを取得
n, c = map(int, input().split())

# x1, v1..xN, vNを取得
xs = []
vs = []
for _i in range(n):
    x, v = map(int, input().split())
    xs.append(x)
    vs.append(v)

r1, r2, l1, l2 = [[], [], [], []]
r_sum, l_sum = [0, 0]
for i in range(n):
    r_sum += vs[i]
    r1.append(r_sum - xs[i])
    r2.append(r_sum - 2 * xs[i])

    i_rev = n - i - 1
    l_sum += vs[i_rev]
    l1.append(l_sum - (c - xs[i_rev]))
    l2.append(l_sum - 2 * (c - xs[i_rev]))

r1_max, r2_max = [0, 0]
l1_max, l2_max = [0, 0]
r1_maxs, r2_maxs = [[0], [0]]
l1_maxs, l2_maxs = [[0], [0]]
for i in range(n):
    r1_max = max(r1_max, r1[i])
    r1_maxs.append(r1_max)
    r2_max = max(r2_max, r2[i])
    r2_maxs.append(r2_max)
    l1_max = max(l1_max, l1[i])
    l1_maxs.append(l1_max)
    l2_max = max(l2_max, l2[i])
    l2_maxs.append(l2_max)

r1_l2_max = 0
l1_r2_max = 0
for i in range(0, n + 1):
    r1_l2_max = max(r1_l2_max, r1_maxs[i] + l2_maxs[n - i])
    l1_r2_max = max(l1_r2_max, l1_maxs[i] + r2_maxs[n - i])

total_max = max(r1_l2_max, l1_r2_max)

# 結果を出力
print("{}".format(total_max))
### BUGGY CODE ###

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
C = []
for _ in range(m):
    b, c = map(int, input().split())
    C.extend([c] * b)
C = sorted(C, reverse=True)

ans = 0
for i in range(n):
    try:
        ans += max(A[i], C[i])
    except IndexError:
        ans += A[i]

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1], reverse=True)

ans = 0
j = 0
for b, c in BC:
    for i in range(b):
        if j < n:
            ans += max(c, A[j])
            j += 1
        else:
            break

if j < n:
    for i in range(n - j):
        ans += A[n - 1 - i]

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

from collections import Counter
n,k,l = map(int, input().split())
def f(m):
    a = [[] for _ in range(n)]
    for _ in range(m):
        p,q = map(int, input().split())
        a[p-1].append(q-1)
        a[q-1].append(p-1)
    b = list(range(n))
    for i in range(n):
        s = [i]
        while s:
            j = s.pop()
            if b[j] != j:
                continue
            b[j] = i
            for k in a[j]:
                s.append(k)
    return b
a = f(k)
b = f(l)
c = Counter((a[i],b[i]) for i in range(n))
print(' '.join((str(c[a[i],b[i]]) for i in range(n))))

### FIXED CODE ###

from collections import Counter
n,k,l = map(int, input().split())
def f(m):
    a = list(range(n))
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p,q = map(int, input().split())
        i = g(p-1)
        j = g(q-1)
        a[j] = i
    return g
g = f(k)
h = f(l)
c = Counter((g(i),h(i)) for i in range(n))
print(' '.join((str(c.get((g(i),h(i)), 1)) for i in range(n))))
### BUGGY CODE ###

n = int(input())
l = []
count = 0
for i in range(n):
    a = int(input())
    if a in l:
        l.remove(a)
        count -= 1
    else:
        l.append(a)
        count += 1
print(count)

### FIXED CODE ###

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

l = sorted(a)
same = 1
count = 0
for i in range(1, n):
    if l[i] == l[i - 1]:
        same += 1
        continue
    if same % 2 == 1:
        count += 1
    same = 1
if same % 2 == 1:
    count += 1
print(count)
### BUGGY CODE ###

n, a, b = map(int,input().split())
ball = []
while len(ball) < n:
    for x in range(a):
        ball.append("b")
        if len(ball) >= n:
            break
    for x in range(b):
        ball.append("r")
        if len(ball) >= n:
            break

print(ball.count("b"))

### FIXED CODE ###

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

k = a * (n // (a+b))
l = min(n % (a + b),a)

print(k + l)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(1000):
        d0 = str(i % 10)
        d1 = str((i // 10) % 10)
        d2 = str((i // 100) % 10)
        j = 0
        found = False
        while j < N:
            if S[j] == d0:
                found = True
                j += 1
                break
            j += 1
        if not found:
            continue
        found = False
        while j < N:
            if S[j] == d1:
                found = True
                j += 1
                break
            j += 1
        if not found:
            continue
        found = False
        while j < N:
            if S[j] == d2:
                found = True
                j += 1
                break
            j += 1
        if not found:
            continue
        if found:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(1000):
        d0 = str(i % 10)
        d1 = str((i // 10) % 10)
        d2 = str((i // 100) % 10)
        j = 0
        found = False
        while j < N:
            if S[j] == d0:
                found = True
                j += 1
                break
            j += 1
        if not found:
            continue
        found = False
        while j < N:
            if S[j] == d1:
                found = True
                j += 1
                break
            j += 1
        if not found:
            continue
        found = False
        while j < N:
            if S[j] == d2:
                found = True
                j += 1
                break
            j += 1
        if not found:
            continue
        if found:
            ans += 1
    print(ans)

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

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)])
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)

### FIXED CODE ###

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)
### BUGGY CODE ###

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

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = map(int, input().split())
        E[x - 1].append(y - 1)
        E[y - 1].append(x - 1)

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb = (tb * w) % MOD
            tw = (tw * (w + b)) % MOD
        return tb, tw
    return sum(dp(0)) % MOD


print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = map(int, input().split())
        E[x - 1].append(y - 1)
        E[y - 1].append(x - 1)

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb, tw
    return sum(dp(0)) % (10 ** 9 + 7)


print(main())
### BUGGY CODE ###

N,K = map(int,input().split())
a = abs(N-K)
if N%K==0: print (0)
else:
    while True:
        c = abs(N-K)
        if c > a: break
        a = c
        N = c
    print(a)

### FIXED CODE ###

N,K = map(int, input().split())
N = N%K
absolute = abs(K-N)
print(absolute if absolute < N else N)
### BUGGY CODE ###

# your code goes here
a=int(input())
if a%2 == 0:
	k = a
else:
	k = a + 1
while k>0:
	if k %2== 0 and k % a ==0:
		print(k)
		quit()
	k = k + 2

### FIXED CODE ###

a=int(input())
if a%2 == 0:
	print(a)
else:
	print(a*2)
### BUGGY CODE ###

import re
n0=input()
s=input()
ans=0

for i in range(1000):
    n = str(i).zfill(3)
#    print(n[0])
    p = ".*"+ n[0] + ".*" + n[1] + ".*" + n[2] +".*"
    if re.match(p,s):
        ans += 1
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    start=0
    f=0
    
    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start = idx + 1
            f+=1
        else:
            break

    if f == 3:
        ans += 1

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

n,m = map(int,input().split())
vals = []
inf = float("inf")
ans = [inf]*2**n

for i in range(m):
	a,b = map(int,input().split())
	C = list(map(int,input().split()))
	cur = 0
	for c in C:
		cur += 2**(c-1)
	ans[cur] = min(ans[cur],a)

for i,a in enumerate(ans):
	if a == inf: continue
	for j,b in enumerate(ans):
		if b == inf: continue
		ans[i|j] = min(ans[i|j],ans[i]+ans[j])

if ans[-1] == inf:
	print(-1)
else:
	print(ans[-1])

### FIXED CODE ###

n,m = map(int,input().split())
vals = []
inf = float("inf")
res = [inf]*2**n

for i in range(m):
	a,b = map(int,input().split())
	C = list(map(int,input().split()))
	cur = 0
	for c in C:
		cur |= 2**(c-1)
	res[cur] = min(res[cur],a)

ans = []
for i,r in enumerate(res):
	if res[i] == inf:
		continue
	ans.append([i,r])


for i,a in ans:
	for j in range(2**n):
		res[i|j] = min(res[i|j],res[i]+res[j])

if res[-1] == inf:
	print(-1)
else:
	print(res[-1])
### BUGGY CODE ###

n=int(input())
l1=input().split()
l=[int(x)for x in l1]
ans=0
for i in range(n):
    list_now=l[0:i+1]
    num_now=l[i]
    list_now.sort()
    if num_now==list_now[0]:
        ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
ans=0
min=2*100000
for i in range(n):
    num_now=l[i]
    if num_now<=min:
        ans+=1
        min=num_now
print(ans)