Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
# セグメント木
# segment tree
import sys
input = sys.stdin.readline

class segmented_tree:
    X_unit = 0
    X_f = lambda self, a, b: max(a,b)
    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (2*N)
        
    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x 
        # 後ろから入れていく
        for i in range(self.N-1, 0, -1):
            self.X[i] = self.X_f(self.X[i<<1], self.X[i<<1|1])

    # 1点更新
    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i<<1],self.X[i<<1|1])
    
    # 区間取得
    def fold(self, l, r):
        l += self.N
        r += self.N
        vl = self.X_unit
        vr = self.X_unit
        # 外から決めていく
        while l < r:
            # print(l,r)
            if l & 1:
                vl = self.X_f(vl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.X_f(vr, self.X[r])
            l >>= 1
            r >>= 1
        return self.X_f(vl,vr)
n,k = map(int, input().split())
As = [int(input()) for i in range(n)]
mx = 300001
ans = 0
sg = segmented_tree(mx)

for i, a in enumerate(As):
    l = max(0,a-k)
    r = min(mx,a+k)
    upd = sg.fold(l,r+1)
    sg.set_val(a, upd+1)
    ans = max(ans, upd+1)
print(ans)



Fixed submission:
import sys
input = sys.stdin.readline

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

# N: 処理する区間の長さ

INF = 0

mx = 300001
LV = (mx-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

update(As[0],As[0]+1,1)
for i, a in enumerate(As[1:]):
    l = max(0,a-k)
    r = min(mx,a+k)
    upd = query(l,r+1)
    if upd == -1:continue
    # print("i",i,"a",a,"upd",upd,"l",l,"r",r)
    update(a, a+1, upd+1)

ans = 0
for a in set(As):
    ans = max(ans,query(a,a+1))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = input()
As = list(map(int, input().split()))
import math
gcd = As[0]
for a in As[1:]:
    tmp = gcd
    gcd = math.gcd(tmp, a)

if gcd > 1:
    print("not coprime")
    exit()
flg = 0
lcd = As[0]
prod = As[0]
for a in As[1:]:
    if math.gcd(a,lcd) != 1:
        print("setwise coprime")
        exit()
    lcd = a*lcd//math.gcd(a,lcd)
 
print("pairwise coprime")

    

Fixed submission:
import math

n = input()
As = list(map(int, input().split()))
gcd = As[0]
for a in As[1:]:
    tmp = gcd
    gcd = math.gcd(tmp, a)

if gcd > 1:
    print("not coprime")
    exit()

era = [0] * (10**6 + 1)
for a in As:
    era[a] += 1
for d in range(2, 10**6+1):
    data = [i for i in range(d,10**6+1,d)]
    cnt = 0
    for i in data:
        cnt += era[i] 
    if cnt > 1:
        print("setwise coprime")
        exit()
print("pairwise coprime")
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))
ps = [p-1 for p in ps]
visited = [False] * n
from collections import defaultdict
from collections import deque
ds = []
sums = []
for i in range(n):
    if visited[i]: continue
    q = deque([])
    q.append(i)
    s = cs[i]
    d = [i]
    while len(q) > 0:
        u = q.popleft()
        visited[u] = True
        nx = ps[u]
        if visited[nx]: continue
        d.append(nx)
        q.append(nx)
        s += cs[nx]
    sums.append(s)
    ds.append(d)

# print(ds,sums)
def calcmax(d,s,k,cs):
    cnt = 0
    l = len(d)
    div, rest_ = divmod(k-1, l)
    rest_ += 1
    if s > 0:
        cnt += div*s
    d2 = d*2
    mx = - 1<<50

    for rest in range(1,rest_+1):
        for i in range(rest,l*2):
            # print(i,d2[i-rest:i])
            c_ = [cs[j] for j in (d2[i-rest:i])]
            c = sum(c_)
            mx = max(mx, c)
    # print(d,cnt,mx)
    return cnt + mx

ans = -1 << 50
for d,s in zip(ds,sums):
    # print("aaa",d,s)
    c = calcmax(d,s,k,cs)
    ans = max(ans,c)
print(ans)

Fixed submission:
n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))
ps = [p-1 for p in ps]
visited = [False] * n
from collections import deque
ds = []
sums = []
for i in range(n):
    if visited[i]: continue
    q = deque([])
    q.append(i)
    s = cs[i]
    d = [i]
    while len(q) > 0:
        u = q.popleft()
        visited[u] = True
        nx = ps[u]
        if visited[nx]: continue
        d.append(nx)
        q.append(nx)
        s += cs[nx]
    sums.append(s)
    ds.append(d)

# print(ds,sums)
from itertools import accumulate
def calcmax(d,s,k,cs):
    cnt = 0
    l = len(d)
    div, rest_ = divmod(k-1, l)
    rest_ += 1
    if s > 0:
        cnt += div*s
    d2 = d*2
    c_ = [cs[j] for j in d2]
    acc = list(accumulate(c_))
    mx = - 1<<50
    if s < 0:
        for rest in range(1,l+1):
            for i in range(rest,l*2):
                c = acc[i] - acc[i-rest]
                mx = max(mx,c)
        return mx
    for rest in range(1,rest_+1):
        for i in range(rest,l*2):
            c = acc[i] - acc[i-rest]
            # print(i,rest,c,"debug")
            mx = max(mx, c)
    # print(d,cnt,mx)
    return cnt + mx

ans = -1 << 50
for d,s in zip(ds,sums):
    # print("aaa",d,s)
    c = calcmax(d,s,k,cs)
    ans = max(ans,c)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H,W,k = map(int, input().split())
# アイテムが何処に何個あるか
fs = [[0]*(W+1) for i in range(H+1)]
for i in range(k):
    h, w, v = map(int, input().split())
    h -= 1
    w -= 1
    fs[h][w] = v

mvs = [(0,1),(1,0)]
dp = [[[-1<<50 for i in range(W+1)] for j in range(H+1)] for k in range(4)]
# dp[n][i][j] n個取ったときの、i,jにおけるアイテム価値の最大値
from collections import deque
q = deque([])
q.append((0,0))
dp[0][0][0] = 0
dp[1][0][0] = fs[0][0]
for h in range(H):
    for w in range(W):
        dp[0][h][w+1] = max(dp[0][h][w+1], dp[0][h][w])
        dp[1][h][w+1] = max(dp[1][h][w+1], dp[1][h][w], dp[0][h][w] + fs[h][w+1])
        dp[2][h][w+1] = max(dp[2][h][w+1], dp[2][h][w], dp[1][h][w] + fs[h][w+1])
        dp[3][h][w+1] = max(dp[3][h][w+1], dp[3][h][w], dp[2][h][w] + fs[h][w+1])
    for w in range(W):
        mx = 0
        for i in range(4):
            # print("fe",i,h,w,"dp",dp[i][h][w])
            mx = max(mx,dp[i][h][w])
        dp[0][h+1][w] = mx
        dp[1][h+1][w] = mx + fs[h+1][w]

H -= 1
W -= 1
ans0 = dp[0][H][W]
ans1 = dp[1][H][W]
ans2 = dp[2][H][W]
ans3 = dp[3][H][W]
# print(fs)
# for i in range(3):
#     d = dp[i]
#     for r in d:
#         print(*r)
#     print("----------")
print(max(ans1,ans2,ans3))

Fixed submission:
H,W,k = map(int, input().split())
# アイテムが何処に何個あるか
fs = [[0]*(W+1) for i in range(H+1)]
for i in range(k):
    h, w, v = map(int, input().split())
    h -= 1
    w -= 1
    fs[h][w] = v

mvs = [(0,1),(1,0)]
dp = [[[-1<<50 for i in range(W+1)] for j in range(H+1)] for k in range(4)]
# dp[n][i][j] n個取ったときの、i,jにおけるアイテム価値の最大値
from collections import deque
q = deque([])
q.append((0,0))
dp[0][0][0] = 0
dp[1][0][0] = fs[0][0]
for h in range(H):
    for w in range(W):
        dp[0][h][w+1] = max(dp[0][h][w+1], dp[0][h][w])
        dp[1][h][w+1] = max(dp[1][h][w+1], dp[1][h][w], dp[0][h][w] + fs[h][w+1])
        dp[2][h][w+1] = max(dp[2][h][w+1], dp[2][h][w], dp[1][h][w] + fs[h][w+1])
        dp[3][h][w+1] = max(dp[3][h][w+1], dp[3][h][w], dp[2][h][w] + fs[h][w+1])
    for w in range(W):
        mx = 0
        for i in range(4):
            # print("fe",i,h,w,"dp",dp[i][h][w])
            mx = max(mx,dp[i][h][w])
        dp[0][h+1][w] = mx
        dp[1][h+1][w] = mx + fs[h+1][w]

H -= 1
W -= 1
ans0 = dp[0][H][W]
ans1 = dp[1][H][W]
ans2 = dp[2][H][W]
ans3 = dp[3][H][W]
# print(fs)
# for i in range(3):
#     d = dp[i]
#     for r in d:
#         print(*r)
#     print("----------")
print(max(ans1,ans2,ans3))
Buggy python submission (verdict: Runtime Error):
n,q = map(int, input().split())
cs = list(map(int, input().split()))

prevs = [-1] * n
# 左端
sts = [-1] * n
for i,c in enumerate(cs):
    if prevs[c] != -1:
        sts[prevs[c]] = i
    prevs[c] = i

qs = [[] for i in range(n)] 
for i in range(q):
    l,r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r,i))

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)

    def add(self, x, w):
        while x <= self.n:
            self.bit[x] += w
            x += x&-x

    def sum(self, x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= x&-x
        return cnt

bit = BIT(n)
ans = [0] * q
for l in range(n-1,-1,-1):
    # 矢印を追加
    if sts[l] != -1:
        bit.add(sts[l], 1)
    for r,i in qs[l]:
        cnt = bit.sum(r)
        ans[i] = r - l + 1 - cnt

print(*ans, sep="\n")

Fixed submission:
n,q = map(int, input().split())
cs = list(map(int, input().split()))

prevs = [-1] * (n+1)
# 左端
sts = [-1] * n
for i,c in enumerate(cs):
    c -= 1
    if prevs[c] != -1:
        sts[prevs[c]] = i
    prevs[c] = i

qs = [[] for i in range(n)] 
for i in range(q):
    l,r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r,i))

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)

    def add(self, x, w):
        while x <= self.n:
            self.bit[x] += w
            x += x&-x

    def sum(self, x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= x&-x
        return cnt

bit = BIT(n)
ans = [0] * q
for l in range(n-1,-1,-1):
    # 矢印を追加
    if sts[l] != -1:
        bit.add(sts[l], 1)
    for r,i in qs[l]:
        cnt = bit.sum(r)
        ans[i] = r - l + 1 - cnt

print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
As = list(map(int, input().split()))

prod = 1
for i in range(k):
    prod *= As[i]
prods = [prod]

for i in range(k, n):
    prod //= As[i-k]
    prod *= As[i]
    prods.append(prod)
# print(*prods)
prev = prods[0]
for i in range(1,len(prods)):
    if prev < prods[i]:
        print("Yes")
    else:
        print("No")
    prev = prods[i]

Fixed submission:
n, k = map(int, input().split())
As = list(map(int, input().split()))


for i in range(k, n):
    if As[i-k] < As[i]:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d = map(int,input().split())
mod = 998244353

dp = [[0] * (d+1) for i in range(c+1)]
dp[a][b] = 1

for i in range(a,c+1):
    for j in range(b,d+1):
        dp[i][j] += dp[i-1][j] * j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %=mod
print(dp[c][d])

Fixed submission:
a,b,c,d = map(int,input().split())
mod = 998244353

dp = [[0] * (d+1) for i in range(c+1)]
dp[a][b] = 1

for i in range(a,c+1):
    for j in range(b,d+1):
        dp[i][j] += dp[i-1][j] * j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %=mod
print(dp[c][d])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(0)
    exit()

Ss = sorted(As)
primes = set()
cnt = 0
d = defaultdict(int)
As = [False] * 10**6
for s in Ss:
    d[s] += 1
    if d[s] == 2:
        As[s] = True
# print(Ss)
for s in set(Ss):
    if As[s]: continue
    else:
        cnt += 1
        ind = 1
        while s * ind < 10**6:
            As[s*ind] = True
            ind += 1
print(cnt)

Fixed submission:
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(1)
    exit()

Ss = sorted(As)
cnt = 0
d = defaultdict(int)
As = [False] * (10**6+10)

for s in Ss:
    d[s] += 1

for s in Ss:
    if As[s]:continue
    else:
        if d[s] == 1:
            cnt += 1
        ind = 1
        while s * ind <= 10**6:
            As[s*ind] = True
            ind += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
n,k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(k):
    imos = [0] * (n+1)
    for i,a in enumerate(As):
        l = max(0, i-a)
        r = min(n, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    acc = list(accumulate(imos))
    # 指数関数的に増えるので、capする
    if acc[:-1] == As:
        print(*As)
        exit()
    As = acc[:-1]
print(*As)

Fixed submission:
from itertools import accumulate
n,k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(k):
    imos = [0] * (n+1)
    for i,a in enumerate(As):
        l = max(0, i-a)
        r = min(n, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    acc = list(accumulate(imos))
    # 指数関数的に増える
    if acc[:-1] == As:
        print(*As)
        exit()
    As = acc[:-1]
print(*As)
Buggy python submission (verdict: Time Limit Exceeded):
"""
Asの部分集合Tの部分集合Uについて考える

1. Tに属さない
2. Tに属し、Uに属さない
3. Tに属し、Uに属す

の3通り考えられる。
i番目までにおいて、部分集合Uの和がkになる⇨dp[i][k]

遷移としては
dp[i+1][k] = dp[i][k] * 2 # 1.2
dp[i+1][k+A[i]] += dp[i][k]
"""
n,s = map(int, input().split())
As  = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    a = As[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        if j + a <= s:
            dp[i+1][j+a] += dp[i][j]
        dp[i+1][j] %= mod
    
            

ans = 0
print(dp[n][s]%mod)



Fixed submission:
"""
Asの部分集合Tの部分集合Uについて考える

1. Tに属さない
2. Tに属し、Uに属さない
3. Tに属し、Uに属す

の3通り考えられる。
i番目までにおいて、部分集合Uの和がkになる⇨dp[i][k]

遷移としては
dp[i+1][k] = dp[i][k] * 2 # 1.2
dp[i+1][k+A[i]] += dp[i][k]
"""
n,s = map(int, input().split())
As  = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    a = As[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        if j + a <= s:
            dp[i+1][j+a] += dp[i][j]
        dp[i+1][j] %= mod
    
            

ans = 0
print(dp[n][s]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
As  = list(map(int, input().split()))

if n == 0:
    if As[0] == 1: print(1)
    else: print(-1)
    exit()
    
# 下から見る
As_r = As[::-1]
p = As_r[0]
# とりうる最大値
a_pre = p
qs = [p]
# とりうる最小値
mn = As_r[0]

# 深さ n-1から0まで
for i,a in enumerate(As_r[1:]):
    d = n - i - 1
    p = min(2**d, p + a)
    mn = (mn+1)//2 + a
    a_pre = a
    qs.append(p)

if mn != 1:
    print(-1)
    exit()

qs.reverse()
# print(qs,As)
ans = qs[0]
cnt = qs[0]
# 上から見る
for i in range(1,n+1):
    qs[i] = min(2**i, 2*(qs[i-1]-As[i-1]),qs[i])
print(sum(qs))

Fixed submission:
from itertools import accumulate
n = int(input())
As = list(map(int, input().split()))

if n == 0:
    if As[0] == 1:print(1)
    else:print(-1)
    exit()


if As[0] != 0:
    print(-1)
    exit()

b = 1
ans = 1
acc = list(accumulate(As))
s = acc[-1]
for ac,a in zip(acc[1:], As[1:]):
    # print(s-ac,2*b-a)
    b = min(2*b-a, s-ac)
    if b < 0:
        print(-1)
        exit()
    ans += b+a
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
As = list(map(int, input().split()))

# ps = [0] * (n+1)
# qs = [0] * (n+1)
# ps[-1] = As[-1]
# qs[-1] = As[-1]

p = As[-1]
q = As[-1]
Asr = As[::-1]
qs = [q]
# 深い方から見ていく
for j,a in enumerate(Asr[1:]):
    i = n - (j + 1) 
    p = (p+1)//2 + a 
    q = min(q + a, 2**i)

    # 最小値が、2**iを超えると、深さ0畳めないのでアウト
    if p > 2**i:
        print(-1)
        exit()
    
    # 2**iを超えない範囲での最大値
    qs.append(q)    
    
if p != 1:
    print(-1)
    exit()
qs.reverse()

qs[0] = 1
ans = 1
for i in range(1,n+1):
    if qs[i] > 2**i:
        qs[i] = 2 ** i
    if qs[i] > 2*(qs[i-1]-As[i-1]):
        qs[i] = 2 * (qs[i-1]-As[i-1])
    ans += qs[i]
print(ans)

Fixed submission:
from itertools import accumulate
n = int(input())
As = list(map(int, input().split()))

if n == 0:
    if As[0] == 1:print(1)
    else:print(-1)
    exit()


if As[0] != 0:
    print(-1)
    exit()

b = 1
ans = 1
acc = list(accumulate(As))
s = acc[-1]
for ac,a in zip(acc[1:], As[1:]):
    # print(s-ac,2*b-a)
    b = min(2*b-a, s-ac)
    if b < 0:
        print(-1)
        exit()
    ans += b+a
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, K = map(int, input().split())
As = list(map(int, input().split()))

# doubling
m = 0
while 2**m < K:
    m += 1
d = [[0] * n for i in range(m)]
for i in range(n):
    d[0][i] = As[i] - 1 

for k in range(m-1):
    for i in range(n):
        d[k+1][i] = d[k][d[k][i]]

now = 0
for k in range(m):
    if (K >> k) & 1:
        now = d[k][now]

print(now+1)


Fixed submission:
n,k = map(int, input().split())
As = list(map(int, input().split()))

visited = [-1] * n
cnt = 0
n = 0
while True:
    visited[n] = cnt
    nx = As[n] - 1
    cnt += 1
    # ループ入った場合
    if visited[nx] != -1:
        first = visited[nx]
        if k <= first:
            for i,v in enumerate(visited):
                if v == k:
                    print(i+1)
                    exit()    
        a = (k-first)%(cnt-first)
        loop = [v-first for v in visited]
        for i,x in enumerate(loop): 
            if x == a:
                print(i+1)
                exit()
        break
    n = nx
Buggy python submission (verdict: Runtime Error):
n,m,k = map(int, input().split())
mod = 998244353

def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,n+1):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] %mod
    # 計算
    if n<k: return 0
    if n<0 or k<0: return 0
    
    modcombs = [1]
    for k in range(1,n+1):
        modcombs.append(fac[n]*(finv[k]*finv[n-k]%mod)%mod)
    return modcombs

mods = modconb(n-1,n-1,mod)
# print(mods)
cnt = 0
for i in range(k+1):
    cnt += m*mods[i]*pow(m-1,n-i-1,mod)
    cnt %= mod
print(cnt)

Fixed submission:
n,m,k = map(int, input().split())
mod = 998244353

def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,n+1):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] %mod
    # 計算
    if n<k: return 0
    if n<0 or k<0: return 0
    
    modcombs = [1]
    for k in range(1,n+1):
        modcombs.append(fac[n]*(finv[k]*finv[n-k]%mod)%mod)
    return modcombs

if n == 1:
    print(m)
    exit()

mods = modconb(n-1,n-1,mod)
cnt = 0
for i in range(k+1):
    cnt += m*mods[i]*pow(m-1,n-i-1,mod)
    cnt %= mod
print(cnt)


# cnt = 100
# for i in range(99):
#     cnt *= 99
#     cnt %= mod

# print(cnt)
Buggy python submission (verdict: Runtime Error):
# 重複順列　19C10
from itertools import combinations_with_replacement as cw

n,m,q = map(int, input().split())
a_candidates = cw([i+1 for i in range(m)],m)
fs = [list(map(int, input().split())) for i in range(q)]

def calc(fs,As):
    cnt = 0
    for a,b,c,d in fs:
        a -= 1
        b -= 1
        if As[b]-As[a] == c: cnt += d
    return cnt

ans = 0
for As in list(a_candidates):
    ans = max(ans, calc(fs,As))

print(ans)

Fixed submission:
# 重複順列　19C10
from itertools import combinations_with_replacement as cw

n,m,q = map(int, input().split())
a_candidates = cw([i+1 for i in range(m)],n)
fs = [list(map(int, input().split())) for i in range(q)]

def calc(fs,As):
    cnt = 0
    for a,b,c,d in fs:
        a -= 1
        b -= 1
        if As[b]-As[a] == c: cnt += d
    return cnt

ans = 0
for As in list(a_candidates):
    ans = max(ans, calc(fs,As))

print(ans)

Buggy python submission (verdict: Runtime Error):
# 重複順列　19C10
from itertools import combinations_with_replacement as cw

n,m,q = map(int, input().split())
a_candidates = cw([i+1 for i in range(m)],m)
fs = [list(map(int, input().split())) for i in range(q)]

def calc(fs,As):
    cnt = 0
    for a,b,c,d in fs:
        if As[b]-As[a] == c: cnt += d
    return cnt

ans = 0
for As in list(a_candidates):
    ans = max(ans, calc(fs,As))

print(ans)

Fixed submission:
# 重複順列　19C10
from itertools import combinations_with_replacement as cw

n,m,q = map(int, input().split())
a_candidates = cw([i+1 for i in range(m)],n)
fs = [list(map(int, input().split())) for i in range(q)]

def calc(fs,As):
    cnt = 0
    for a,b,c,d in fs:
        a -= 1
        b -= 1
        if As[b]-As[a] == c: cnt += d
    return cnt

ans = 0
for As in list(a_candidates):
    ans = max(ans, calc(fs,As))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,n = map(int, input().split())

def f(x):
    return (a*(x%b)-(a*b)%b)//b

ans = 0
for i in range(min(n+1,b+1)):
    ans = max(f(i),ans)
print(ans)

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

mx = a*n//b
if n//b < 1:
    print(mx)
else:
    x = (a*b-a)//b
    print(x)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
from collections import deque
"""
行き ⇨ dp LIS計算とstack登録
帰り ⇨ stackをpop dp巻き戻し
"""

n = int(input())
As = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)


INF = 10**10
dp = []
pos = 0
ans = [0] * n
q = deque([])
def dfs(v,p):
    global pos
    # 行き
    a = As[v]
    ind = bisect_left(dp, a)
    if ind == len(dp): 
        dp.append(a)
        # 引数の1つ目はappendしたか
        q.append((True, -1, -1))
    else:
        # 更新
        tmp = dp[ind]
        dp[ind] = a
        q.append((False,ind,tmp))

    ans[v] = len(dp)
    for u in edges[v]:
        if u == p:continue
        dfs(u,v)
        # 帰り        
        isappend, ind, tmp = q.pop()
        if isappend:
            dp.pop()
        else:
            dp[ind] = tmp
        
    
dfs(0,-1)

print(*ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

from bisect import bisect_left
from collections import deque
"""
行き ⇨ dp LIS計算とstack登録
帰り ⇨ stackをpop dp巻き戻し
"""

n = int(input())
As = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)


INF = 10**10
dp = []
pos = 0
ans = [0] * n
q = deque([])
def dfs(v,p):
    global pos
    # 行き
    a = As[v]
    ind = bisect_left(dp, a)
    if ind == len(dp): 
        dp.append(a)
        # 引数の1つ目はappendしたか
        q.append((True, -1, -1))
    else:
        # 更新
        tmp = dp[ind]
        dp[ind] = a
        q.append((False,ind,tmp))

    ans[v] = len(dp)
    for u in edges[v]:
        if u == p:continue
        dfs(u,v)
        # 帰り        
        isappend, ind, tmp = q.pop()
        if isappend:
            dp.pop()
        else:
            dp[ind] = tmp
        
    
dfs(0,-1)

print(*ans)