Harryxun/stf_run huggingface dataset:
n = int(input())
A = [int(input()) for i in range(n)]
count = 0


def insertionSort(A, n, g):
    global count
    for i in range(g,n):
        v = A[i]
        j = i - g
        
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            count += 1
        A[j+g] = v

def shellSort(A, n):
    global count
    G = [i for i in range(1,n) if i % 3 == 1]  
    m = len(G)
    G = G[::-1]
    for i in G:
        insertionSort(A, n, i)
    return A, G, m 


A, G, m = shellSort(A, n)
print (m)
print (G)
print (cnt)
for i in range(len(A)):
    print (A[i])

### FIXED CODE ###

import math

def insertionSort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v
    return cnt


def shellSort(A, n):
    cnt = 0
    j = int(math.log(2 * n + 1, 3)) + 1
    G = list(reversed([(3 ** i - 1)// 2 for i in range(1, j)]))
    m = len(G)
    for i in range(m):
        cnt += insertionSort(A, n, G[i])
    return A, cnt, G, m

n = int(input())
A = [int(input()) for i in range(n)]
ans, count, G, m = shellSort(A, n)
print(m)
print(' '.join(map(str,G)))
print(count)
[print(i) for i in A]
from collections import deque
n, u, v = map(int, input().split())
u-=1; v-=1;
a = []; b = [];
dist = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    dist[a].append(b)
    dist[b].append(a)

def bfs(u):
    d = [-1]*n
    stack = deque([u])
    d[u] = 0
    while len(stack)!=0:
        s = stack.popleft()
        for t in dist[s]:
            if d[t]==-1:
                d[t] = d[s]+1
                stack.append(t)
    return d

A = bfs(v)
T = bfs(u)
ans=0
for i in range(n):
    if A[i]>d[i]:
        ans = max(A[i]-1, ans)
print(ans)

### FIXED CODE ###

from collections import deque
n, u, v = map(int, input().split())
u-=1; v-=1;
a = []; b = [];
dist = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    dist[a].append(b)
    dist[b].append(a)

def bfs(u):
    d = [-1]*n
    stack = deque([u])
    d[u] = 0
    while len(stack)!=0:
        s = stack.popleft()
        for t in dist[s]:
            if d[t]==-1:
                d[t] = d[s]+1
                stack.append(t)
    return d

A = bfs(v)
T = bfs(u)
ans=0
for i in range(n):
    if A[i]>T[i]:
        ans = max(A[i]-1, ans)
print(ans)
n = int(input())
for i in range(900):
    x = list(n)
    if x[0]==x[1]==x[2]:
        print(n)
        break 
    n+=1


### FIXED CODE ###

n = input()
if n[0] == n[1] == n[2]:
    ans = n
elif n[1] > n[0] or (n[1] == n[0] and n[2] > n[0]):
    ans = str(int(n[0])+1)*3
elif n[1] <= n[0] or n[2] < n[0]:
    ans = n[0]*3
print(ans)
n = input()
a = list(map(int, input().split()))
min = a[1]
ans = 0            
for i in a:
	if min > i:
		ans += min - i
	else:
		min = i

print(ans) 

### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
max = 0
step = 0            
for i in a:
	if max > i:
		step += max - i
	else:
		max = i

print(step)
a, b = int(input())
c = a*b
if c % 2 == 0:
  print("Even")
  else:
    print("Odd)

### FIXED CODE ###

a,b = input().split()
result = int(a) * int(b)
     
if result % 2 == 0:
	print("Even")
else :
	print("Odd")
valores = [int(input()), int(input()), int(input())]
valores.remove(max(valores))
print(valores[0]+valores[1])


### FIXED CODE ###

a = [int(x) for x in input().split()]
a.sort()
print(a[0] + a[1])
def main():
    inputs = input()

    roop_num = len(inputs)
    if roop_num >= 100000:
        cnt = 0

    else:
        cnt = 0
        flag = False
        for start in range(roop_num-3):
            roop_num_end = roop_num - start
            ans_list = []
            ans_list = [int(inputs[start:end+start+4]) for end in range(roop_num_end-3) if int(inputs[start:end+start+4]) % 2019 == 0]

            cnt += len(ans_list)

    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    inputs = input().split(' ')
    sheep = int(inputs[0])
    wolf = int(inputs[1])

    if sheep > wolf:
        print('safe')

    else:
        print('unsafe')

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

def dfs(v, u, d):
    if d % 2 == 0:
        even.append(v)
    else:
        odd.append(v)
    for i in g[v]:
        if i == u:
            continue
        dfs(i, v, d + 1)
    return

N = int(input())
g = [[] for _ in range(N)]
odd = []
even =[]
ans = [-1] * N
nums = [[], [], []]
for i in range(1, N + 1):
    nums[i % 3].append(i)
sanlst = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

dfs(0, 0, 0)
zCnt = N // 3

if len(even) <= zCnt:
    for node in even:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in odd:
        ans[node] = rest.pop()
elif len(even) <= zCnt:
    for node in odd:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in even:
        ans[node] = rest.pop()
else:
    for i in nums[1]:
        ans[even.pop()] = i
    for i in nums[2]:
        ans[odd.pop()] = i
    for i in even:
        ans[i] = nums[0].pop()
    for i in odd:
        ans[i] = nums[0].pop()

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def dfs(v, u, d):
    if d % 2 == 0:
        even.append(v)
    else:
        odd.append(v)
    for i in g[v]:
        if i == u:
            continue
        dfs(i, v, d + 1)
    return

N = int(input())
g = [[] for _ in range(N)]
odd = []
even =[]
ans = [-1] * N
nums = [[], [], []]
for i in range(1, N + 1):
    nums[i % 3].append(i)
sanlst = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

dfs(0, -1, 0)
zCnt = len(nums[0])

if len(even) <= zCnt:
    for node in even:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in odd:
        ans[node] = rest.pop()
elif len(odd) <= zCnt:
    for node in odd:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in even:
        ans[node] = rest.pop()
else:
    for i in nums[1]:
        ans[even.pop()] = i
    for i in nums[2]:
        ans[odd.pop()] = i
    rest = nums[0]
    for i in even:
        ans[i] = rest.pop()
    for i in odd:
        ans[i] = rest.pop()

print(*ans)
S, T = str(input().split(' '))
A, B = int(input().split(' '))
U = str(input())

if S == U:
  A -= 1
if T == U:
  B -= 1
print(A, B)


### FIXED CODE ###

S, T = input().split()
A, B = map(int, input().split())
U = input()

if S == U:
  print(A - 1, B)
else:
  print(A, B - 1)
A,B =map(int, input().split())

print( X + Y/2)

### FIXED CODE ###

X,Y = map(int, input().split())

print(X + Y//2)
H, W = map(int, input().split())
lis=[["."]*(W+2)]
for i in range(H):
    lis+=[["."]+list(input())+["."]]
lis += [["."]*(W+2)]
print(lis)
for w in range(1, H+1):
    for h in range(1, W+1):
        x=0
        if lis[h][w] == ".":
            if lis[h+1][w-1] == "#":
                x += 1
            if lis[h+1][w] == "#":
                x += 1
            if lis[h+1][w+1] == "#":
                x += 1
            if lis[h][w-1] == "#":
                x += 1
            if lis[h][w+1] == "#":
                x += 1
            if lis[h-1][w-1] == "#":
                x += 1
            if lis[h-1][w] == "#":
                x += 1
            if lis[h-1][w+1] == "#":
                x += 1
            lis[h][w] = x
lis=lis[1:-1]
for i in lis:
    print(*i[1:-1], sep="")

### FIXED CODE ###

h, w = map(int, input().split())
S=[]
S.append(["."] * (w + 2))
for i in range(h):
  S.append(["."] + list(input()) + ["."])
S.append(["."] * (w + 2))
 
 
for i in range(1, h+1):
  for j in range(1, w+1):
    counter = 0
    if S[i][j] == ".":
      if S[i-1][j-1] == "#":
        counter += 1
      if S[i-1][j] == "#":
        counter += 1
      if S[i-1][j+1] == "#":
        counter += 1
      if S[i][j-1] == "#":
        counter += 1
      if S[i][j+1] == "#":
        counter += 1
      if S[i+1][j-1] == "#":
        counter += 1
      if S[i+1][j] == "#":
        counter += 1
      if S[i+1][j+1] == "#":
        counter += 1
      S[i][j] = counter
 
for i in range(1,h+1):
  for j in range(1, w+1):
    print(S[i][j], end="")
  print()
#! /usr/bin/env python3
import itertools
N, A, B = map(int, input().split())
t = B - A + 1
s = set()
if B <= A or N < 3:
    if A == B:
        print(1)
    else:
        print(0)
else:
    print(len({sum(i) for i in itertools.product(range(t), repeat = N - 2)}))

### FIXED CODE ###

#! /usr/bin/env python3
import itertools
N, A, B = map(int, input().split())
if B <= A or N < 2:
    if A == B:
        print(1)
    else:
        print(0)
else:
    print((B - A) * (N - 2) + 1)
import numpy as np
import sys
H, W, M = map(int, input().split())
d = np.zeros((H, W), dtype=int)
for _ in range(M):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    d[h, w] = 1
tate = np.sum(d, axis=0)
yoko = np.sum(d, axis=1)
tate_max = tate.max()
yoko_max = yoko.max()

ans_tate, ans_yoko = [], []
for i in range(W):
    if tate[i] == tate_max:
        ans_tate.append(i)
for i in range(H):
    if yoko[i] == yoko_max:
        ans_yoko.append(i)

for h in ans_yoko:
    for w in ans_tate:
        if d[h, w] != 1:
            print(tate_max+yoko_max)
            sys.exit()
print(tate_max+yoko_max-1)

### FIXED CODE ###

import sys
H, W, M = map(int, input().split())
h_list, w_list = [0]*H, [0]*W
check = set()
for _ in range(M):
    h, w = map(int, input().split())
    check.add((h-1, w-1))
    h_list[h-1] += 1
    w_list[w-1] += 1
h_max, w_max = max(h_list), max(w_list)
h_bom = [i for i in range(H) if h_list[i]==h_max]
w_bom = [i for i in range(W) if w_list[i]==w_max]
for h in h_bom:
    for w in w_bom:
        if not (h, w) in check:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)
#ABC070C
import math
from functools import reduce
N=int(input())
T=[int(input()) for i in range(N)]
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
print(reduce(lcm_base, T))

### FIXED CODE ###

#ABC070C
import math
from functools import reduce
N=int(input())
T=[int(input()) for i in range(N)]
#def lcm_base(x, y):
#    interium=x//math.gcd(x, y)
#    return (interium*y)
#print(reduce(lcm_base, T))
ans=1
def grcode(x, y):
    if y==0:
        return (x)
    else:
        return grcode(y, x%y)
for i in range(N-1):
    T[i]=T[i]//grcode(T[i],T[i+1])
    T[i+1]=T[i]*T[i+1]
print(T[N-1])
a = map(int, input().split())
if a.count(5) == 2 and a.count(7) == 1:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

a = list(map(int, input().split()))
if a.count(5) == 2 and a.count(7) == 1:
    print('YES')
else:
    print('NO')
import numpy as np
h,w,m = map(int,input().split())
bomb = list(tuple(map(lambda x: int(x)-1,input().split())) for i in range(m))
Map= np.zeros((h,w))
for i in bomb:
    Map[i] = 1
print(Map)

bombx = np.count_nonzero(Map,axis=0)
bomby = np.count_nonzero(Map,axis=1)
print(bombx)
maxx = max(bombx)
maxy = max(bomby)

maxx_index = np.where(bombx == maxx)
maxy_index = np.where(bomby == maxy)
flag = 0
print(maxx_index[0],maxy_index[0])
for i in maxx_index[0]:
    for j in maxy_index[0]:
        if Map[i][j] == 0:
            flag = 1
if flag == 0:
    print(maxx+maxy)
else:
    print(maxx+maxy-1)


### FIXED CODE ###

h,w,m = map(int,input().split())
bombX = [0]*h
bombY = [0]*w
bomb = set()
maxX = maxY = 0
for i in range(m):
    i,j = map(lambda x:int(x)-1, input().split())
    bomb.add((i,j))
    bombX[i] += 1
    bombY[j] += 1
    maxX = max(maxX,bombX[i])
    maxY = max(maxY,bombY[j])
maxX_index = list(i for i in range(h) if bombX[i] == maxX)
maxY_index = list(i for i in range(w) if bombY[i] == maxY)
for i in maxX_index:
    for j in maxY_index:
        if (i,j) in bomb: continue
        print(maxX+maxY)
        exit()
print(maxX+maxY-1)
import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = [0 for _ in range(HK+1)]
H = [0 for _ in range(WK+1)]
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

HMAXES = []
WMAXES = []
answer = 0
HMAX = max(H)
WMAX = max(W)


# 3*10^5
for i, h in enumerate(H):
    if h == HMAX:
        HMAXES.append(i)
for i, w in enumerate(W):
    if w == WMAX:
        HMAXES.append(i)
# 3*10^5
answer = HMAX + WMAX
for i, h in enumerate(HMAX):
    for j, w in enumerate(WMAX):
        if HW[i][j] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

### FIXED CODE ###

import sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = {}
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[(h,w)] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if not (h,w) in HW:
            print(answer)
            sys.exit(0)
print(answer-1)
def red_or_blue(N, s):
  s_1 = [x for x in s]
  l_r = s_1.count('R')
  l_b = s_1.count('B')
  if l_r > l_b:
    return 'Yes'
  else:
    return 'No'

i = input().split() 

N = i[0]
s = i[1]
print(red_or_blue(N, s))

### FIXED CODE ###

def red_or_blue(N, s):
  s_1 = [x for x in s]
  l_r = s_1.count('R')
  l_b = s_1.count('B')
  if l_r > l_b:
    return 'Yes'
  else:
    return 'No'

i = [input() for i in range(2)]
N = i[0]
s = i[1]
print(red_or_blue(N, s))
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]

queue = []
visited = [] 
for i in range(h):
    T = [0]*w
    visited.append(T) 
    
for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            count = 0
            p = 0
            while len(queue) > 0:
              now = queue.pop(0)
              for i in range(4):
                y = now[0]+dy_dx[i][0]
                x = now[1]+dy_dx[i][1]
                if 0 <= y < h and 0 <= x < w:
                  if C[y][x] != '#' and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]]+1
                    queue.append([y,x])
                    if p == 0:
                      count += 1
                      p += 1
              p = 0
        for i in range(h):
          for j in range(w):
            ans = max(ans,visited[i][j])
        queue = []
        visited = [] 
        ans = 0
        for i in range(h):
            T = [0]*w
            visited.append(T) 
            
       
            
        
print(ans-1)

### FIXED CODE ###

h,w = map(int,input().split())
C = [list(input()) for i in range(h)]

queue = []
visited = [] 
ans = 0
for i in range(h):
    T = [0]*w
    visited.append(T) 


for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            while len(queue) > 0:
                now = queue.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if C[y][x] != '#' and visited[y][x] == 0:
                            visited[y][x] = visited[now[0]][now[1]]+1
                            queue.append([y,x])
                    
        for ii in range(h):
            for jj in range(w):
                ans = max(ans,visited[ii][jj])
            
        queue = []
        visited = [] 
        for l in range(h):
            T = [0]*w
            visited.append(T) 
                        
        
print(ans-1)
var = input()

pas = var ** var

print(pas)

### FIXED CODE ###

var = int(input())

pas = var ** 3

print(pas)
a = [int(input()) for i in range(5)]
r = 10
fix = 10000
for i in range(5):
    if a[i] % 10 == 0:
        fix = i
    elif a[i] % 10 < r:
        last = i
        r = int(a[i] % 10)

if fix == 10000:
    b = []
    for i in range(5):
        if i != last:
            b.append(a[i])
    
    b = [int((b[i] + 9) / 10) * 10 for i in range(4)] 

    time = 0
    for i in range(4):
        time = time + b[i]
    
    time = time + a[last]


else:
    b = []
    for i in range(5):
        if i != fix and i != last:
            b.append(a[i])

    b = [int((b[i] + 9) / 10) * 10 for i in range(3)]

    time = 0
    for i in range(3):
        time = time + b[i]

    time = time + a[fix] + a[last]

print(time)

### FIXED CODE ###

a = [int(input()) for i in range(5)]
r = 10
last = 0
for i in range(5):
    if a[i] % 10 != 0 and a[i] % 10 < r:
        last = i
        r = int(a[i] % 10)


b = [int((a[i] + 9) / 10) * 10 for i in range(5)] 
time = 0
for i in range(5):
    if i != last:
        time = time + b[i]
    
time = time + a[last]
print(time)
n, p=map(int,input().split())
ans = 0
if n != 1:
    for i in range(1,int((p+1)**(1/2))+1):
        ni = i**n
        if p/ni >= 1 and p/ni == int(p/ni):
            ans = i
        elif p/ni < 1:
            break
    print(ans)
else:
    print(p)


### FIXED CODE ###

n, p=map(int,input().split())
ans = 0
if n != 1:
    for i in range(1,int((p+1)**(1/n))+1):
        ni = i**n
        if p/ni >= 1 and p/ni == int(p/ni):
            ans = i
        elif p/ni < 1:
            break
    print(ans)
else:
    print(p)
import sys

s = sys.stdin()
c = 0
l = len(s)
for i in range(l/2):
  if s[0] != s[l-i]:
    c += 1
print(c)

### FIXED CODE ###

import sys

s = sys.stdin.read().strip()
c = 0
l = len(s)
for i in range(int(l/2)):
  if s[i] != s[l-i-1]:
    c += 1
print(c)
def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    #root = [[1000000000 for i in range(N)] for i in range(N)]
    #for i, j, k in ABC:
     #   root[i - 1][j - 1] = k
      #  root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替えのタプル
        return itertools.permutations(list_name, len(list_name))

    for i in range(N):
        for j in range(N):
            for k in range(N):
                root[i][j] = min(root[i][j], root[i][k] + root[k][j])
    #a = kumiawase(r)
    #ans = 10000000000
    #for i in a:
     #   key = 0
      #  for j in range(len(i) - 1):
       #     key += root[i[j] - 1][i[j + 1] - 1]
        #ans = min(ans, key)
    #print(ans)
ABC073D()

### FIXED CODE ###

def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)


    from scipy.sparse import csgraph
    root = csgraph.floyd_warshall(root)

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
ABC073D()
k = int(input())
    s = input()
    if len(s) <= k:
        print(s)
    else:
        print(s[:k]+'...')

### FIXED CODE ###

k = int(input())
s = input()
if k >= len(s):
  print(s)
else:
  print(s[:k]+"...")
#d-even relation
n=int(input())
visitedlist=[-1 for  i in range(n)]
lists=[tuple(map(int,input().split())) for i in range(n-1)]
kilist=[[] for i in range(n)]
for i in lists:
    kilist[i[0]-1].append([i[1],i[2]])
    kilist[i[1]-1].append([i[0],i[2]])   
anslist=[0 for i in range(n)]
#開始地点1のところは0を基準としている
#1には初めに訪れる
searchedlist=[0 for i in range(n)]
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==0:
                    search(k[0])
                else:
                    pass
        else:
            pass

search(1)
for i in anslist:
    print(i%2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)
from bisect import bisect

N = int(input())
a = list(map(int,input().split()))
g = [[] for _ in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = [0]*N
def dfs(t,f,l,seq):
    l = l.copy()
    seq = seq.copy()
    l.append(a[t])
    i = bisect(seq,l[-1])
    if len(seq)==i:
        seq.append(l[-1])
    else:
        seq[i]=l[-1]
    ans[t] = len(seq)
    for v in g[t]:
        if v != f:
            dfs(v,t,l,seq)
dfs(0,0,[],[])
for i in range(N):
    print(ans[i])

### FIXED CODE ###

from bisect import bisect_left as bisect
import sys
sys.setrecursionlimit(10**9)

N = int(input())
a = list(map(int,input().split()))
g = [[] for _ in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = [0]*N
def dfs(t,f,l):
    res = 0
    i = bisect(l,a[t])
    if len(l)==i:
        l.append(a[t])
    else:
        res = [i,l[i]]
        l[i]=a[t]
    ans[t] = len(l)
    for v in g[t]:
        if v != f:
            back = dfs(v,t,l)
            if back:
                l[back[0]] = back[1]
            else:
                l.pop()
    return res
dfs(0,0,[])
for i in range(N):
    print(ans[i])