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

N, W =map(int, raw_input().split())

weights = []
values = []
for i in range(N):
    wi, vi =map(int, raw_input().split())
    weights.append(wi)
    values.append(vi)

sum_v = sum(values)

INF = 10**9+7

dp = [[INF]*(sum_v+1) for _ in range(N+1)]
dp[0][0] = 0
#dp[0][values[0]] = weights[0]                                                                                         


for i in range(N):
    wi = weights[i]
    vi = values[i]
    for j in range(sum_v+1):
        if j < vi:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-vi]+ wi)

for j in range(sum_v+1):
    if dp[N][j] <= W:
        ans = j

print ans


### FIXED CODE ###

def main():
    N, W =map(int, input().split())

    weights = []
    values = []
    for i in range(N):
        wi, vi =map(int, input().split())
        weights.append(wi)
        values.append(vi)

    sum_v = sum(values)

    INF = 10**9+7

    dp = [[INF]*(sum_v+1) for _ in range(N+1)]
    dp[0][0] = 0


    for i in range(N):
        wi = weights[i]
        vi = values[i]
        for j in range(sum_v+1):
            if j < vi:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-vi]+ wi)

    for j in range(sum_v+1):
        if dp[N][j] <= W:
            ans = j

    print(ans)

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

import heapq
n = int(input())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, input().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, input().split())
dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
used = [False]*(n+1)

for i in range(n+1):
    dist[i][i] = 0
        
def dijkstra(s, dist):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(n+1):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
        
    return dist
dist = dijkstra(k, dist)

for _ in range(q):
    x, y = map(int, input().split())
    if used[x] == False:
        dist = dijkstra(x, dist)
        used[x] = True
    print(dist[x][k]+dist[k][y])

### FIXED CODE ###

import heapq
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

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

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


q, k = map(int, input().split())
dist, _ = dijkstra(n, edges, k-1)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])
### BUGGY CODE ###

N=int(input())

#bit探索
def bit():
    for i in range(2 **N):
        op = []
        tmp=0
        for j in range(N):
            if ((i >> j) & 1):
                op.append(j+1)
                tmp += (j+1)
        if tmp == N:
            return op

li=bit()

for k in li:
    print(k)

### FIXED CODE ###

N=int(input())


start=int((2*N+1)**0.5)

for i in range(3):
    i += start
    if i*(i+1) >= 2*N:
        ret = i
        delete=i*(i+1)/2 - N
        break

for k in range(1,ret+1):
    if k != delete:
        print(k)
### BUGGY CODE ###

N=int(input())
plus=[]
minus=[]
for _ in range(N):
    S=input()
    tmp=0
    min_tmp=0 #)))の
    for i in range(len(S)):
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp<0:
            min_tmp=min(min_tmp,tmp)
    tmp=0
    max_tmp=0 #(((の
    for i in range(len(S)):
        i=len(S)-i-1
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp>0:
            max_tmp=max(max_tmp,tmp)
    if tmp>=0:
        plus.append((tmp,max_tmp,-min_tmp))
    else:
        minus.append((tmp,max_tmp,-min_tmp))

plus.sort(key=lambda x:x[2])
minus.sort(reverse=True,key=lambda x:x[1])
ans=0
for i,j,k in plus:
    if ans<k:
        print("No")
        exit()
    ans+=i
for i,j,k in minus:
    if ans<k:
        print("No")
        exit()
    ans+=i
if ans==0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N=int(input())
plus=[]
minus=[]
for _ in range(N):
    S=input()
    tmp=0
    min_tmp=0 #)))の
    for i in range(len(S)):
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp<0:
            min_tmp=min(min_tmp,tmp)
    tmp=0
    max_tmp=0 #(((の
    for i in range(len(S)):
        i=len(S)-i-1
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp>0:
            max_tmp=max(max_tmp,tmp)
    if tmp>=0:
        plus.append((tmp,max_tmp,-min_tmp))
    else:
        minus.append((tmp,max_tmp,-min_tmp))

plus.sort(key=lambda x:x[2])
minus.sort(reverse=True,key=lambda x:x[1])
ans=0
for i,j,k in plus:
    if ans<k:
        print("No")
        exit()
    ans+=i
for i,j,k in minus:
    if ans<k:
        print("No")
        exit()
    ans+=i
if ans==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
nw = [0]*n
nv = [0]*n
for i in range(n):
    nw[i],nv[i] = [int(x) for x in stdin.readline().rstrip().split()]
def knapsack(n,w,nw,nv):
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - nw[i] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-nw[i]]+nv[i])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,nw,nv))

### FIXED CODE ###

from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))
### BUGGY CODE ###

from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)
### BUGGY CODE ###

s = input()

count = 0
while True:
    n = len(s)
    ints = sum(map(int, s))
    if n == 0 or ints == 0 or ints == n:
        break
    sn = s + '\n'
    for i in range(n):
        if sn[i-1] + sn[i] == '10' or sn[i-1] + sn[i] == '01':
            s = sn[:i-1] + sn[i+1:n]
            count += 1
            break

print(count * 2)

### FIXED CODE ###

s = input()

zero = s.count('0')
one = s.count('1')

print(2 * min(zero, one))
### BUGGY CODE ###

A = input()

S = 0
lis = [0] * 2019
lis[0] += 1
l = len(A)+1
d = 1

for n in reversed(A):
    S += int(n)*d
    sm = S % 2019
    lis[sm] += 1
    d *= 10

result = 0

for n in lis:
    result += (n*(n-1)/2)


print(int(result))


### FIXED CODE ###

S = input()
 
res = [0] * 2019
res[0] = 1
 
d = 1
a = 0
 
for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019
 
ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)
### BUGGY CODE ###

N,K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

S = []
cnt = 0
for i in range(K-1,N):
    s = 1
    for j in range(i,i-K,-1):
        s *= A[j]
    S.append(s)
    
    if cnt == 0:
        cnt += 1
        continue
    print("Yes" if S[cnt-1]<S[cnt] else "No")
    cnt += 1

### FIXED CODE ###

N,K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

for i in range(K,N):
    if A[i] / A[i-K] > 1 :
        print("Yes")

    else :
        print("No")
### BUGGY CODE ###

a,b,k = map(int,input().split())
s = set(range(a,a+k))
t = set(range(b-k+1,b+1))
u = (s|t)&set(range(a,b+1))
for i in sorted(u): print(i)

### FIXED CODE ###

a,b,k = map(int,input().split())
s = set(range(a,a+k))
t = set(range(b-k+1,b+1))
u = sorted(s|t)
for i in u:
    if a<=i<=b: print(i)
### BUGGY CODE ###

import numpy as np
# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = [int(v) for v in input().split(" ")]
step = np.arange(len(A_arr))
def Luminate(A_arr, i):
  isLuminated = np.abs(step - i) < np.array(A_arr)+1
  return isLuminated
def get_Intensity(A_arr):
  return [np.sum(Luminate(A_arr, i)) for i in range(len(A_arr))]
Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity)

print(" ".join([str(v) for v in Intensity]))


### FIXED CODE ###

import numpy as np
 
N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))
indexes = np.arange(0, N)
 
dp = np.zeros(shape=N + 1, dtype=np.int64)
 
for k in range(K):
    np.add.at(dp, np.maximum(0, indexes - A), 1)
    np.add.at(dp, np.minimum(N, indexes + A + 1), -1)
    A = dp.cumsum()[:-1]
    if np.all(A == N):
        break
    dp *= 0
 
print(' '.join(map(str, A)))
### BUGGY CODE ###

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

    pow2 = 2**N

    anss = []
    ans = 0
    setMax2s = [set([0])]
    for S in range(1, pow2):
        setMax2 = set([S])
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                setMax2 |= setMax2s[S0]
        Bs = sorted(setMax2, key=lambda x: As[x], reverse=True)
        i, j = Bs[:2]
        ans2 = As[i]+As[j]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        setMax2 = set([i, j])
        setMax2s.append(setMax2)

    print('\n'.join(map(str, anss)))


solve()


### FIXED CODE ###

def solve():
    N = int(input())
    As = list(map(int, input().split())) + [0]

    pow2 = 2**N

    anss = []
    ans = 0
    max2s = [[0, -1]]
    for S in range(1, pow2):
        m1, m2 = S, -1
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                i1, i2 = max2s[S0]
                if m1 == i1:
                    m2 = m2 if As[m2] >= As[i2] else i2
                elif As[m1] >= As[i1]:
                    m2 = m2 if As[m2] >= As[i1] else i1
                else:
                    m2 = m1 if As[m1] >= As[i2] else i2
                    m1 = i1
        ans2 = As[m1]+As[m2]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        max2s.append([m1, m2])

    print('\n'.join(map(str, anss)))


solve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,u,v = map(int,input().split())

edges = [[] for _ in range(n)]

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

stack1 = [u-1]
stack2 = [v-1]

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

while stack1:
    for _ in range(len(stack1)):
        q1 = stack1.pop(0)
        for i in edges[q1]:
            if dis1[i] == -1 and dis2[i] == -1:
                dis1[i] = dis1[q1] + 1
                stack1.append(i)

    for _ in range(len(stack2)):
        q2 = stack2.pop(0)
        for i in edges[q2]:
            if dis2[i] == -1:
                dis2[i] = dis2[q2] + 1
                stack2.append(i)

while stack2:
    q = stack2.pop(0)
    for i in edges[q]:
        if dis2[i] == -1:
            dis2[i] = dis2[q] + 1
            stack2.append(i)

ans = 0
for i in range(n):
    if dis1[i] != -1:
        ans = max(ans, dis2[i])

print(ans-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,u,v = map(int,input().split())
edges = [[] for _ in range(n)]

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

visit1 = [False] * n
visit2 = [False] * n
visit1[u-1] = True
visit2[v-1] = True

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

stack1 = [u-1]
stack2 = [v-1]

while stack1:
    l = stack1.pop(-1)
    for i in edges[l]:
        if visit1[i] == False:
            visit1[i] = True
            dis1[i] = dis1[l] + 1
            stack1.append(i)

while stack2:
    l = stack2.pop(-1)
    for i in edges[l]:
        if visit2[i] == False:
            visit2[i] = True
            dis2[i] = dis2[l] + 1
            stack2.append(i)

ans = 0

for i in range(n):
    if dis1[i] < dis2[i]:
        ans = max(ans, dis2[i])

print(ans-1)
### BUGGY CODE ###

N=int(input())
V1,V2={},{}
ans = N-1
for n,i in enumerate(list(map(int,input().split(' ')))):
    if n%2==0:
        V1.setdefault(i,0)
        V1[i]+=1
    else:
        V2.setdefault(i,0)
        V2[i]+=1
V1=sorted(V1.items(),key=lambda x:x[1])
V2=sorted(V2.items(),key=lambda x:x[1])
cut = max(V1[0][1],V2[0][1])
for i in V1:
    for j in V2:
        if i[1]+j[1] < cut:
            break
        if i[0]!=j[0]:
            ans = min(ans,N-i[1]-j[1])
        else:
            ans = min(ans,N-max(i[1],j[1]))
print(ans)

### FIXED CODE ###

N=int(input())
V1,V2={},{}
ans = N-1
for n,i in enumerate(list(map(int,input().split(' ')))):
    if n%2==0:
        V1.setdefault(i,0)
        V1[i]+=1
    else:
        V2.setdefault(i,0)
        V2[i]+=1
V1=sorted(V1.items(),key=lambda x:x[1],reverse=True)
V2=sorted(V2.items(),key=lambda x:x[1],reverse=True)
cut = max(V1[0][1],V2[0][1])
for i in V1[:2]:
    for j in V2[:2]:
        if i[0]!=j[0]:
            ans = min(ans,N-i[1]-j[1])
        else:
            ans = min(ans,N-max(i[1],j[1]))
print(ans)
### BUGGY CODE ###

from heapq import heappush,heappop
import sys

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A=[A[-1]]+A+[A[0]]
B=[B[-1]]+B+[B[0]]
lst=[]
for i in range(1,N+1):
    heappush(lst,[-B[i],i])

count=0
while lst:
    h,i=heappop(lst)
    h=-h
    if A[i]>=h:
        continue
    h-=B[i-1]+B[i+1]
    count+=1
    B[i]=h
    if i==1:
        B[N+1]=h
    if i==N:
        B[0]=h
    if A[i]<h:
        heappush(lst,[-h,i])
    if h<=0:
        print(-1)
        sys.exit()

for i in range(1,N+1):
    if A[i]!=B[i]:
        print(-1)
        break
else:
    print(count)

### FIXED CODE ###

from heapq import heappush,heappop
import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
lst=[]
for i in range(N):
    heappush(lst,(-B[i],i))

count=0
while lst:
    h,i=heappop(lst)
    h=-h
    x,z=B[i-1],B[(i+1)%N]
    kkk=x+z
    if (h-A[i])%kkk==0:
        count+=(h-A[i])//kkk
        B[i]=A[i]
        continue
    elif kkk>=h:
        print(-1)
        sys.exit()
    else:
        count+=h//kkk
        h=h%kkk
        B[i]=h    
        if A[i]>h:
            print(-1)
            sys.exit()
        heappush(lst,(-h,i))

if A==B:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

from collections import Counter
def factorization(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return Counter(yy)

lcd = dict()
for i in num:
  j = dict(factorization(i))
  for x,y in j.items():
    if not x in lcd.keys():
      lcd[x] = y
    else:
      lcd[x] = max(lcd[x],y)

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

ans =0
for i in range(n):
  ans += lc*modinv(num[i],mod)
  ans %= mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

import fractions
lc = num[0]
for i in range(1, n):
    lc = lc * num[i] // fractions.gcd(lc, num[i])

lc %= mod    
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

ans =0
for i in range(n):
  ans += lc*modinv(num[i],mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

import itertools, functools

h, w = map(int, input().split())
ch, cw = tuple(int(s) - 1 for s in input().split())
dh, dw = tuple(int(s) - 1 for s in input().split())
s = [input() for _ in range(h)]

stack = [(ch, cw)]
score = [[float('inf')] * w for _ in range(h)]
score[ch][cw] = 0
while stack:
    x, y = stack.pop()

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and score[x][y] < score[nx][ny]:
            score[nx][ny] = score[x][y]
            stack.append((nx, ny))
    
    for dx, dy in itertools.product(range(-2, 3), repeat=2):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and score[x][y] + 1 < score[nx][ny]:
            score[nx][ny] = score[x][y] + 1
            stack.append((nx, ny))

if score[dh][dw] == float('inf'):
    print(-1)
else:
    print(score[dh][dw])

### FIXED CODE ###

import collections, itertools

h, w = map(int, input().split())
ch, cw = tuple(int(s) - 1 for s in input().split())
dh, dw = tuple(int(s) - 1 for s in input().split())
s = [input() for _ in range(h)]

q = collections.deque()
q.append((ch, cw, 0))
score = [[float('inf')] * w for _ in range(h)]
score[ch][cw] = 0
while q:
    x, y, p = q.popleft()

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and p < score[nx][ny]:
            score[nx][ny] = p
            q.appendleft((nx, ny, p))
    
    for dx, dy in itertools.product(range(-2, 3), repeat=2):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and p + 1 < score[nx][ny]:
            score[nx][ny] = p + 1
            q.append((nx, ny, p + 1))

if score[dh][dw] == float('inf'):
    print(-1)
else:
    print(score[dh][dw])
### BUGGY CODE ###

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n = int(input())

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
dks=dijkstra(0,n,n-1,cost)
for i in dks:
    if i%2==0:print(0)
    else:print(1)

### FIXED CODE ###

n=int(input())
c=[[] for i in range(n+1)]
d={}
for i in range(n-1):
    x,y,z=map(int,input().split())
    c[x].append(y)
    c[y].append(x)
    d[x,y]=z
d[1,1]=0
stack=[1]
parent=[None]*(n+1)
while stack:
    i=stack.pop()
    for j in c[i]:
        if j==parent[i]:
            continue
        parent[j]=i
        d[1,j]=d[1,i]+d[tuple(sorted([i,j]))]
        stack.append(j)
for i in range(1,n+1):
    print(d[1,i]%2)
### BUGGY CODE ###

from fractions import gcd

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

lcm_num = A[0]
for i in range(1, N):
    g = gcd(lcm_num, A[i])
    lcm_num = lcm_num * A[i] // g
#print(lcm_num)

ans = 0
for i in range(N):
    ans += lcm_num // A[i]
    ans %= mod
print(ans)


### FIXED CODE ###

from copy import deepcopy

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

"""
普通に最小公倍数を計算すると桁数が莫大になって
桁溢れor多倍長整数を使っても計算が一気に遅くなるのがこの問題のミソ

桁数の大きい数は素因数分解の形で保持すると高速にmod計算が可能なので、これを用いる。
まずは1000以下の素数テーブルを用意。
"""
prime = [i for i in range(2, 10**3)]
for p in prime:
    prime = [x for x in prime if (x == p or x % p != 0)]

def div(a, n):
    """
    自然数aがnで何回割れるかと、割り尽くした残りを返す
    """
    num = 0
    while a % n == 0:
        num += 1
        a = a // n
    return num, a

"""
素数pごとに、各A[i]がpで何回割れるかを求め、iでループを回した中での最大値をe_pとすると
A[0],...A[N-1]の最小公倍数はL = ¥Prod_p p^{e_p}になる。
これならmodで桁数削減が可能。

ただし素数テーブルは1000までしか用意してないので、それ以上の素数はリストAの中に吐き出させ、
あとでそれをLに組み込む。
"""
L = 1
for p in prime:
    e = 0
    for i in range(N):
        cand, A[i] = div(A[i], p)
        e = max(e, cand)
    L *= pow(p, e, mod)
    L %= mod
for a in set(A):
    L *= a
    L %= mod

"""
あとは答えを求めるのみ。
ただしLをmodで算出しているので、単純にL/A[i]を加算すると答えが狂う。
そこでA[i]^{-1}をmodで求めてLに乗算する。
"""
ans = 0
for i in range(N):
    inv = pow(B[i], mod - 2, mod)
    ans += L * inv
    ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
p = [0 for i in range(n)]
for i in range(n):
    p[i] = int(input())

visited = [0 for i in range(n)]

for i in reversed(range(n)):
    if visited[i] == 0:
        visited[i] = 1
        count = 1
        target = p[i] - 1
        for j in reversed(range(i)):
            if p[j] == target:
                count += 1
                visited[j] = count
                target -= 1
print(n - max(visited))


### FIXED CODE ###

n = int(input())
p = [0 for i in range(n)]
for i in range(n):
    p[i] = int(input())

visited = [0 for i in range(n+1)]

"""
for i in reversed(range(n)):
    if visited[i] == 0:
        visited[i] = 1
        count = 1
        target = p[i] - 1

        for j in reversed(range(i)):
            if p[j] == target:
                count += 1
                visited[j] = count
                target -= 1
"""
for i in range(n):
    visited[p[i]] = visited[p[i] - 1] + 1
print(n - max(visited))