Harryxun/stf_run huggingface dataset:
n = input()
kakeru = input().split()
kakekake = kakeru[0]
    if n > 4:
        for i in range(n-3):
            kakekake = kakekake * kakeru[i+1]
    elif n == 2:
        kakekake = kakeru[0] + kakeru[1]
    elif n == 3:
        kakekake = kakeru[0] + kakeru[1] + kakeru[2]
    elif n == 4:
        kakekake = kakeru[0] + kakeru[1] + kakeru[2] + kakeru[3]
if kakekake > 10**18:
    print(-1)
print(kakekake)

### FIXED CODE ###

n = int(input())
b = 1
a = list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    for i in range(n):
        b *= a[i]
        if b > 10**18:
            print(-1)
            break
    if b <=10**18:
        print(b)
import numpy as np
n,w = map(int, input().split())

items = list(map(int, input().split()) for _ in range(n))
dp = np.zeros(w+1, dtype='int32')

for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())


### FIXED CODE ###

n,k = [int(i) for i in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(i) for i in input().split()]
    w.append(a)
    v.append(b)

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(k+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
data = []
try:
    while True:
        data.append(raw_input())

except EOFError:
        pass

for i in data:
    a, b, c, d, e, f = i.split()
    a, b, c, d, e, f = int(a), int(b), int(c), int(d), int(e), int(f)
    if abs(a) or abs(b) or abs(c) or abs(d) or abs(e) or abs(f) <= 1000:
        for j in range(-1000, 1001):
            y1 = (c - (a * j)) / float(b)
            y2 = (f - (d * j)) / float(e)
            if y1 == y2:
                print "{:.3f} {:.3f}".format(j, y1)
                break

### FIXED CODE ###

data = []
try:
    while True:
        data.append(raw_input())

except EOFError:
    pass

for i in data:
    a, b, c, d, e, f = map(float, (i.split()))
    if (abs(a) <= 1000
        and abs(b) <= 1000
        and abs(c) <= 1000
        and abs(d) <= 1000
        and abs(e) <= 1000
        and abs(f) <= 1000):
        y = (a*f - c*d) / (a*e - b*d)
        x = (c - b*y) / a
        print "{:.3f} {:.3f}".format(x, y)
N = int(input())
a = [ ]
for i in range(1:10):
    for j in range(i:10):
        b = i*j
        a.append(b)
if a.count(N) == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
a = [ ]
for i in range(1,10):
    for j in range(i,10):
        b = i*j
        a.append(b)
if a.count(N) == 0:
    print('No')
else:
    print('Yes')
MOD = 998244353


def solve(s, k):
    one_count = []
    ones = 0
    for st in s:
        if st == "1":
            ones += 1
        else:
            one_count.append(ones)
            ones = 0
    one_count.append(ones)
    s = sum(one_count)
    m = len(one_count)
    dp = [[[0] * s for _ in range(s)] for __ in range(m + 1)]
    dp[0][0][0] = 1
    for i in range(m):
        c = one_count[i]
        for j in range(s):
            for p in range(s):
                dp[i][j][p] %= MOD
                for q in range(s - max(j, p)):
                    dp[i + 1][j + q][p + q] += dp[i][j][p]
                for q in range(-c, 0):
                    if j + q >= 0:
                        dp[i + 1][j + q][p] += dp[i][j][p]

    # print(dp)
    res = sum([dp[m][0][p] for p in range(min(k + 1, s + 1))])
    # print(res)
    return res % MOD


def main():
    s, k_ = input().split()
    k = int(k_)
    res = solve(s, k)
    print(res)


def test():
    assert solve("0101", 1) == 4
    assert solve("01100110", 2) == 14
    assert solve("1101010010101101110111100011011111011000111101110101010010101010101", 20) == 113434815


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

MOD = 998244353


def solve(s, k):
    one_count = []
    ones = 0
    for st in s:
        if st == "1":
            ones += 1
        else:
            one_count.append(ones)
            ones = 0
    one_count.append(ones)
    ss = sum(one_count)
    # print(ss)
    m = len(one_count)
    dp = [[[0] * (ss + 1) for _ in range(ss + 1)] for __ in range(m + 1)]
    dp[0][0][0] = 1
    for i in range(m):
        c = one_count[i]
        for j in range(ss + 1):
            for p in range(ss + 1):
                dp[i][j][p] %= MOD
                for q in range(ss + 1 - max(j, p)):
                    dp[i + 1][j + q][p + q] += dp[i][j][p]
                for q in range(-c, 0):
                    if j + q >= 0:
                        dp[i + 1][j + q][p] += dp[i][j][p]

    # print(dp)
    res = sum([dp[m][0][p] for p in range(min(k + 1, ss + 1))])
    # print(res)
    return res % MOD


def main():
    s, k_ = input().split()
    k = int(k_)
    res = solve(s, k)
    print(res)


def test():
    assert solve("0101", 1) == 4
    assert solve("01100110", 2) == 14
    assert solve("1101010010101101110111100011011111011000111101110101010010101010101", 20) == 113434815


if __name__ == "__main__":
    test()
    main()
#!/usr/bin/env pytho3
n = int(input())
a = list(map(int,input().split()))
# ３種類の値をもち、自分より前に同じ色の人がa[i]となる組み合わせ
# コーナーケースとして、全部同じ色なら3通り、あとは*6したらいい
# n<=10**5
# 先頭を色１、次にa[i] == 0になった点を色2,3にしてしていい。前から埋める
# 前から見ていって、それぞれの色の今の人数をcolorとして
# color.count(a[i]) == 2　ならans *= 2, ==3 ans *= 3
mod = 10**9 + 7
if a == list(range(n)): print(3)
else:
  k = 0
  ans = 6
  color = [0,0,0]
  for person in range(n):
    #print(color,person)
    bit = 0#すでにcolor == a[i]が出てきているか?
    if a[person] == 0:
      color[k] = 1
      k += 1
      continue
    for num in range(3):
      if color[num] == a[person]:
        bit += 1
        if bit == 1:
          color[num] += 1
      if num == 2: 
        ans *= bit
        ans = ans % mod
  print(ans)


### FIXED CODE ###

#!/usr/bin/env pytho3
n = int(input())
a = list(map(int,input().split()))
# ３種類の値をもち、自分より前に同じ色の人がa[i]となる組み合わせ
# コーナーケースとして、全部同じ色なら3通り、あとは*6したらいい
# n<=10**5
# 先頭を色１、次にa[i] == 0になった点を色2,3にしてしていい。前から埋める
# 前から見ていって、それぞれの色の今の人数をcolorとして
# color.count(a[i]) == 2　ならans *= 2, ==3 ans *= 3
# 2ケースのみRE
mod = 10**9 + 7
if a == list(range(n)): print(3)
else:
  k = 0
  ans = 6
  color = [0,0,0]
  for person in range(n):
    #print(color,person)
    bit = 0#すでにcolor == a[i]が出てきているか?
    if a[person] == 0:
      if k == 3:#REになるケース
        print(0)
        exit()
      color[k] = 1
      k += 1
      continue
    for num in range(3):
      if color[num] == a[person]:
        bit += 1
        if bit == 1:
          color[num] += 1
      if num == 2: 
        ans *= bit
        ans = ans % mod
  print(ans)
n=int(input())
a=list(map(int,input().split()))
plus=[a[i] for i in range(n) if a[i]>=0]
l_plus=len(plus)
minus=[a[i] for i in range(n) if a[i]<0]
l_minus=len(minus)
x_cal=[]
y_cal=[]
if plus!=[] and minus!=[]:
  x_cal.append(minus[0])
  for j in range(1,l_plus-1):
    x_cal.append(x_cal[-1]-plus[j])
  for k in range(1,l_plus):
    y_cal.append(plus[k])
  y_last=x_cal[-1]-y_cal[-1]
  x_cal.append(plus[0])
  for j in range(1,l_minus-1):
    x_cal.append(x_cal[-1]-minus[j])
  for k in range(1,l_minus):
    y_cal.append(minus[k])
  y_cal.append(y_last)
  print(x_cal[-1]-y_cal[-1])
  for ii in range(n-1):
    print(x_cal[ii],y_cal[ii])
elif minus==[]:
  a.sort()
  print(sum(a)-2*a[0])
  x_cal.append(a[0])
  for ij in range(1,n-2):
    x_cal.append(x_cal[-1]-a[ij])
  for jj in range(0,n-2):
    y_cal.append(a[jj+1])
  y_cal.append(x_cal[-1]-y_cal[-1])
  x_cal.append(a[-1])
  for ii in range(n-1):
    print(x_cal[ii],y_cal[ii])
else:
  a.sort()
  print(a[-1]*2-sum(a))
  x_cal.append(a[-1])
  for ij in range(1,n-2):
    x_cal.append(x_cal[-1]-a[ij])
  for jj in range(0,n-2):
    y_cal.append(a[jj+1])
  x_cal.append(x_cal[-1]-y_cal[-1])
  y_cal.append(a[0])
  for ii in range(n-1):
    print(x_cal[ii],y_cal[ii])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
plus=[a[i] for i in range(n) if a[i]>=0]
l_plus=len(plus)
minus=[a[i] for i in range(n) if a[i]<0]
l_minus=len(minus)
x_cal=[]
y_cal=[]
if n==2:
  a.sort()
  print(a[1]-a[0])
  print(a[0],a[1])
else:
  if plus!=[] and minus!=[]:
    if l_plus>1:
      x_cal.append(minus[0])
    for j in range(1,l_plus-1):
      x_cal.append(x_cal[-1]-plus[j])
    for k in range(1,l_plus):
      y_cal.append(plus[k])
    if l_plus>1:
      y_last=x_cal[-1]-y_cal[-1]
    else:
      y_last=minus[0]
    x_cal.append(plus[0])
    for j in range(1,l_minus):
      x_cal.append(x_cal[-1]-minus[j])
    for k in range(1,l_minus):
      y_cal.append(minus[k])
    y_cal.append(y_last)
    print(x_cal[-1]-y_cal[-1])
    for ii in range(n-1):
      print(x_cal[ii],y_cal[ii])
  elif minus==[]:
    a.sort()
    print(sum(a)-2*a[0])
    x_cal.append(a[0])
    for ij in range(1,n-2):
      x_cal.append(x_cal[-1]-a[ij])
    for jj in range(0,n-2):
      y_cal.append(a[jj+1])
    y_cal.append(x_cal[-1]-y_cal[-1])
    x_cal.append(a[-1])
    for ii in range(n-1):
      print(x_cal[ii],y_cal[ii])
  else:
    a.sort()
    print(a[-1]*2-sum(a))
    x_cal.append(a[-1])
    for ij in range(1,n-2):
      x_cal.append(x_cal[-1]-a[ij])
    for jj in range(0,n-2):
      y_cal.append(a[jj+1])
    x_cal.append(x_cal[-1]-y_cal[-1])
    y_cal.append(a[0])
    for ii in range(n-1):
      print(x_cal[ii],y_cal[ii])
[s,t]=input().split();
cnt = 0;
for i in range(len(s)):
    if s[i] != t[i] :
        cnt=cnt+1;
print(cnt);


### FIXED CODE ###

#[s,t]=input().split();
s=input();
t=input();
cnt = 0;
for i in range(len(s)):
    if s[i] != t[i] :
        cnt=cnt+1;
        
print(cnt);
import copy

def main():
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a%b)

    def lcm(a, b):
        return (a // gcd(a, b)) * b

    n, m = map(int, input().split())
    # これだと72がREになる
    A = set([int(x) for x in input().split()])
    # これだと74も78もREになる
    # A = [int(x) for x in input().split()]
    A_ = copy.deepcopy(A)
    a_lcm = A.pop()
    # Aの要素が複数ならlcmを計算する
    if len(A) >= 1:
        for a in A:
            a_lcm = lcm(a_lcm, a)
    else:
        a_lcm = a_lcm
    # 元のAの値とlcmの半分の値を割り切れるものがあったら0
    for i in A_:
        if (a_lcm / 2) % i == 0:
            print(0)
            exit()
        else:
            continue
    # mがlcmの半分よりも小さかったら0
    if a_lcm / 2 > m:
        print(0)
    else:
        # あとは定数倍の数調べて終わり
        # ans = int((m - (a_lcm / 2))) // a_lcm + 1
        ans = int((m - (a_lcm / 2)) // a_lcm) + 1
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
# from math import gcd


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b
def main():
    n, m = map(int, input().split())
    A = set([int(x) for x in input().split()])
    a_lcm = 1
    for a in A:
        a_lcm = lcm(a_lcm, a)
        # mがlcmの半分よりも小さかったら0
        if (a_lcm / 2) > m:
            print(0)
            exit()
    for a in A:
        if (a_lcm / 2) % a == 0:
            print(0)
            exit()
    # # あとは定数倍の数調べて終わり
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)

if __name__ == '__main__':
    main()
n, a = map(int, input().split())
X = tuple(map(int, input().split()))
dp = [[[0] * (n*max(X)+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    # i枚目までで
    for j in range(n):
        # j枚のカードを選んで
        for s in range(n*max(X)+1):
            # 合計がsになるパターン
            if dp[i][j][s] == 0:
                continue
            # i枚目のカードが選ばれない場合
            dp[i+1][j][s] += dp[i][j][s]
            # i枚目のカードが選ばれる場合
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)


### FIXED CODE ###

n, a = map(int, input().split())
X = tuple(map(int, input().split()))
dp = [[[0] * (2550) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    # i枚目までで
    for j in range(n):
        # j枚のカードを選んで
        for s in range(n*a+1):
            # 合計がsになるパターン
            if dp[i][j][s] == 0:
                continue
            # i枚目のカードが選ばれない場合
            dp[i+1][j][s] += dp[i][j][s]
            # i枚目のカードが選ばれる場合
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)
N,C,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
A.sort()
k=K
a=0
c=C
j=1
while j<N:
    k-=A[j]-A[j-1]
    n-=1
    if k>0 and c>0:    
        j+=1
    else:     
        a+=1
        c=C
        k=K
        j+=1
print(a+1)   

### FIXED CODE ###

N,C,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
A.sort()
k=K
a=0
c=C-1
j=1
while j<N:
    k-=A[j]-A[j-1]
    c-=1
    if k>=0 and c>=0:    
        j+=1
    else:     
        a+=1
        c=C-1
        k=K
        j+=1
print(a+1)
n,x=map(int,input().split())
if x==1 or x==2*n-1:
  print("No")
else:
  print("Yes")
  l=[0]*(2*n-1)

  l[n-2]=x-1
  l[n-1]=x
  l[n]=x+1
  l[n+1]=x-1
  print(*l,sep="\n")
  

### FIXED CODE ###

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

if n==2 and x==2:
  print("Yes",*[1,2,3],sep="\n")
elif x==1 or x>=2*n-1:
  print("No")
else:
  print("Yes")
  if x==2:
    t=[4,2,1,3]
  else:
    t=[x-1,x+1,x,x-2]
  p=[i for i in range(1,2*n) if i not in t]
  print(*p[:n-3]+t+p[n-3:],sep="\n")
N = int(input())
count = 0
for X in range(N):
    for i in range(1, int(X**0.5)+1):
        if X % i == 0:
            count += 1
            if i != X // i:
                count += 1
  print(count)

### FIXED CODE ###

N = int(input())
ans = 0
for A in range(1,N):
  ans += (N-1) // A
print(ans)
import math,functools

n,x =map(int,input().split())
if n==1:
    print(abs(int(input())-x))
else:
    lis = list(map(int,input().split()))
    for i in range(n):
        lis[i] = abs(lis[i]-x)
    print(functools.reduce(math.gcd,lis))


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N,X=map(int,input().split())
x=[abs(X-int(i)) for i in input().split()]
print(reduce(gcd,x))
import numpy as np
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
a_a=np.ones( N+1 )
for i in range(M):
    a_a[a[i]]=0
c=np.zeros(N+1)
c[0]=1
for i in range(1,N+1):
    if i==1:
        c[i]=c[i-1]*a_a[i-1]
    else:
        c[i]=c[i-1]*a_a[i-1]+c[i-2]*a_a[i-2]
print(int(c[N])%(7+10**9))

### FIXED CODE ###

N,M=map(int,input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
j = 0
dp[0] = 1
mod = 10**9+7
for i in range(1, N+1):
    if j < M and i == a[j]:
        j += 1
    elif i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-1]+dp[i-2]) % mod
print(dp[N])
import heapq
x,y,z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
q = []
heapq.heapify(q)
heapq.heappush(q,(-(a[0] + b[0] + c[0]),0,0,0))
for _ in range(K):
    m, i, j, k = heapq.heappop(q) #mに和、ijkにインデックス
    print(-m) #親から取り出すが、親は子よりも小さい、大きい順にするために-を入れている
    if i + 1 < X: #最初にiには０が挿入されている,pythonではインデックスが０から始まるから<xでいい
        s = (-(A[i+1] + B[j] + C[k]), i+1, j, k)
        if s not in q:
            heapq.heappush(q,s)
    if j + 1 < Y:
        s = (-(A[i] + B[j+1] + C[k]), i, j+1, k)
        if s not in q:
            heapq.heappush(q, s)
    if k + 1 < Z:
        s = (-(A[i] + B[j] + C[k+1]), i, j, k+1)
        if s not in q:
            heapq.heappush(q,s)
    

### FIXED CODE ###

import heapq
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
q = []
heapq.heapify(q)
heapq.heappush(q,(-(A[0] + B[0] + C[0]),0,0,0))
for _ in range(K):
    m, i, j, k = heapq.heappop(q) #mに和、ijkにインデックス
    print(-m) #親から取り出すが、親は子よりも小さい、大きい順にするために-を入れている
    if i + 1 < X: #最初にiには０が挿入されている,pythonではインデックスが０から始まるから<xでいい
        s = (-(A[i+1] + B[j] + C[k]), i+1, j, k)
        if s not in q:
            heapq.heappush(q,s)
    if j + 1 < Y:
        s = (-(A[i] + B[j+1] + C[k]), i, j+1, k)
        if s not in q:
            heapq.heappush(q, s)
    if k + 1 < Z:
        s = (-(A[i] + B[j] + C[k+1]), i, j, k+1)
        if s not in q:
            heapq.heappush(q,s)
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

if max(c) < 0:
    res = max(c)
else:
    res = 0

for i in range(n):
    score = []
    s = 0
    pos = i
    visited = [False] * n
    while True:
        if visited[pos]:
            break

        visited[pos] = True
        s += c[p[pos]-1]
        score.append(s)
        pos = p[pos] - 1

    loop = len(score)

    if k < loop:
        res = max(res, max(score[:k]))
    elif score[-1] <= 0:
        res = max(res, max(score))
    else:
        res = max(res, score[-1] * (k // loop) + max(score[:k%loop]), score[-1] * (k // loop - 1) + max(score))

print(res)

### FIXED CODE ###

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

if max(c) < 0:
    res = max(c)
else:
    res = 0

for i in range(n):
    score = []
    s = 0
    pos = i
    visited = [False] * n
    loop = 0
    while True:
        if visited[pos]:
            break

        visited[pos] = True
        s += c[p[pos]-1]
        score.append(s)
        pos = p[pos] - 1
        loop += 1

    if k < loop:
        res = max(res, max(score[:k]))
    elif score[-1] <= 0:
        res = max(res, max(score))
    elif k % loop == 0:
        res = max(res, score[-1] * (k // loop), score[-1] * (k // loop - 1) + max(score))
    else:
        res = max(res, score[-1] * (k // loop) + max(score[:k%loop]), score[-1] * (k // loop - 1) + max(score))

print(res)
# -*- coding: utf-8 -*-

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

temp_plus = ("1" * a) + ("0" * b)
temp = ""
while len(temp) <= n:
    temp += temp_plus

print(temp[0:n].count("1"))


### FIXED CODE ###

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

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

temp = n // (a + b)
amari = n % (a + b)
result = temp * a

if amari >= a:
    result += a
else:
    result += amari

print(result)
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod = 10 ** 9 + 7

N, M, K = LS()
desk = LSR(2)
a, b = [0], [0]

# a = [0, 0 + A1, 0 + A1 + A2, ....]
# b = [0, 0 + B1, 0 + B1 + B2, ....]
for i in range(N):
    a.append(a[i] + desk[0][i])
for j in range(M):
    b.append(b[j] + desk[1][j])

# a + b <= K を求める　⇒　変形してb >= K - a とすることで、
# aは全件トライ、bのみ選択可能な最大値を算出することで計算量をO(N + M)に抑える
ans, j = 0, M 

for i in range(N + 1):
    if a > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

print(ans)

### FIXED CODE ###

import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod = 10 ** 9 + 7

N, M, K = LI()
desk = LIR(2)
a, b = [0], [0]

# a = [0, 0 + A1, 0 + A1 + A2, ....]
# b = [0, 0 + B1, 0 + B1 + B2, ....]
for i in range(N):
    a.append(a[i] + desk[0][i])
for j in range(M):
    b.append(b[j] + desk[1][j])

# a + b <= K を求める　⇒　変形してb >= K - a とすることで、
# aは全件トライ、bのみ選択可能な最大値を算出することで計算量をO(N + M)に抑える
ans, j = 0, M 

for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

print(ans)
l = input().split()
a = int(l[0])
b = int(l[1])
if (a * b) % 2 = 1:
  print(Odd)
else:
  print(Even)

### FIXED CODE ###

l = input().split()
a = int(l[0])
b = int(l[1])
if (a * b) % 2 == 1:
  print("Odd")
else:
  print("Even")
from collections import defaultdict, deque
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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, K = map(int, input().split())
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]

log = [float('inf')]*N
log[0] = 0
q = deque([0])
ans = K
while q:
  p = q.popleft()
  if log[p]<1:
    ans *= cmb(K-1,K-1-len(dic[p]),mod)
  else:
    ans *= cmb(K-2,K-1-len(dic[p]),mod)
  ans %= mod
  for e in dic[p]:
    if log[e]>log[p]+1:
      q += [e]
      log[e] = log[p]+1
print(ans)

### FIXED CODE ###

from collections import defaultdict, deque
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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, K = map(int, input().split())
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]

log = [float('inf')]*N
log[0] = 0
q = deque([0])
ans = K
while q:
  p = q.popleft()
  if log[p]<1:
    ans *= cmb(K-1,K-1-len(dic[p]),mod)
  else:
    ans *= cmb(K-2,K-1-len(dic[p]),mod)
  ans %= mod
  for e in dic[p]:
    if log[e]>log[p]+1:
      q += [e]
      log[e] = log[p]+1
print(ans)
def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    # print(tree)

    ans = [1] * N
    # dfs
    from bisect import bisect_left
    def dfs(u, par, dp: list):
        if A[u] > dp[-1]:
            dp.append(A[u])
        else:
            dp[bisect_left(dp, A[u])] = A[u]
        ans[u] = max(ans[u], len(dp))
        for v in tree[u]:
            if v != par:
                dfs(v, u, dp)
                val = dp.pop()
                if val < A[u]:
                    dp.append(A[u])

    dfs(0, -1, [A[0]])

    for i in range(N):
        print(ans[i])



if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(2*(10**5)+1)
    main()


### FIXED CODE ###

from bisect import bisect_left


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    ans = [1] * N

    # dfs
    def dfs(u, par):
        nonlocal ans
        nonlocal dp
        pos = bisect_left(dp, A[u])
        old = dp[pos]
        dp[pos] = A[u]

        ans[u] = bisect_left(dp, float("inf")) - 1

        for v in tree[u]:
            if v == par:
                continue
            dfs(v, u)

        dp[pos] = old

    dp = [float("inf")] * (N+1)
    dp[0] = float("-inf")
    dfs(0, -1)

    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    main()