Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return (ans/2)%(10**9+7)

Fixed submission:
n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))

Buggy python submission (verdict: Runtime Error):
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return (ans/2)%(10**9+7)

Fixed submission:
n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))

Buggy python submission (verdict: Runtime Error):
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return ans%(10**9+7)

Fixed submission:
n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))

Buggy python submission (verdict: Runtime Error):
a=(int)(input().split())
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=a
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return ans%(10**9+7)

Fixed submission:
n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))

Buggy python submission (verdict: Runtime Error):
a=input().split()
sum=0
for i in a:
  sum+=a
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return ans%(10**9+7)

Fixed submission:
n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))

Buggy python submission (verdict: Runtime Error):
a=map(int,input().split())
sum=0
for i in a:
  sum+=a
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return ans%(10**9+7)

Fixed submission:
n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))
Buggy python submission (verdict: Runtime Error):
n=(int)(nput())
a=input().split()
for i in range(n):
  a[i]=(int)(a[i])
  
dic={}
sum=0
for i in range(n):
  if not a[i] in dic:
    dic[a[i]]=1
  else:
    dic[a[i]]+=1
    sum+=dic[a[i]]-1

for i in a:
  print(sum-dic[i]+1)



Fixed submission:
n=(int)(input())
a=input().split()
for i in range(n):
  a[i]=(int)(a[i])
  
dic={}
sum=0
for i in range(n):
  if not a[i] in dic:
    dic[a[i]]=1
  else:
    dic[a[i]]+=1
    sum+=dic[a[i]]-1

for i in a:
  print(sum-dic[i]+1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

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

if a == 0:
    print(0)
    sys.exit()

lst = []
is_blue = True
count = 0
for i in range(n):
    if is_blue:
        lst.append('b')
        count += 1
        if count == a:
            is_blue = False
            count = 0
    else:
        lst.append('r')
        count += 1
        if count == b:
            is_blue = True
            count = 0

result = list(filter(lambda x:x == 'b', lst))
print(len(result))

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

ans = n // (a + b) * a
rem = n % (a + b)
ans += min(rem, a)
print(ans)
Buggy python submission (verdict: Runtime Error):
D = int(input())
T = int(input())
S = int(input())

if D <= T*S:
    print("Yes")
else:
    print("No")

Fixed submission:
D, T, S = map(int, input().split())

if D <= T*S:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
D = int(input())
T = int(input())
S = int(input())

if D <= T*S:
    print("Yes")
else:
    print("No")

Fixed submission:
D, T, S = map(int, input().split())

if D <= T*S:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(x) for x in input().split()]
cnt = 0
for i in A:
    if i == 0:
        pass
    if A[i-1] > A[i]:
        cnt += 1
    else:
        pass
print(cnt)


Fixed submission:
n = int(input())
A = [int(x) for x in input().split()]
maxv = 0
ans = 0
for a in A:
    if maxv > a:
        ans += maxv - a
    else:
        maxv = a
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 1

for i in a:
    ans *= i

  if ans > 10 ** 18:
      print(-1)

print(ans)

Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 1

for i in a:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        break
else:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 1

for i in a:
    ans *= i

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 1

for i in a:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        break
else:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 1

for i in a:
    ans *= i

if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 1

for i in a:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        break
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = []
for i in range(k):
    ans.append(h[i + k - 1] - h[i])
print(min(ans))

Fixed submission:
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = []
for i in range(n - k + 1):
    ans.append(h[i + k - 1] - h[i])
print(min(ans))

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = []
for i in range(n):
    ans.append(h[i + k - 1] - h[i])
print(min(ans))

Fixed submission:
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = []
for i in range(n - k + 1):
    ans.append(h[i + k - 1] - h[i])
print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
I=int(input())

for h in range(1,3501):
    for n in range(1,3501):
        t = 4*h*n - I*h - I*n
        if t <= 0:
            continue;
        s = I*h*n
        if s % t == 0:
            print(h, n, int(s/t))
            quit()

Fixed submission:
N=int(input())

for h in range(1,3501):
    if (4*h <= N):
        continue
    nn = int (N*h / (4*h-N))
    for n in range(max(1,nn),3501):
        t = 4*h*n - N*h - N*n
        if t <= 0:
            continue
        s = N*h*n
        if s % t == 0:
            print(h, n, int(s/t))
            quit()
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1 = [(Ch, Cw)]
stack2 = []

answer = 0

while 1:
    while stack1:
        sh, sw = stack1.pop()
        stack2.append((sh, sw))
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nh, nw = sh + i, sw + j
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                if nh == Dh and nw == Dw:
                    print(answer)
                    exit()
                grid[nh][nw] = 1
                stack1.append((nh, nw))
    answer += 1

    while stack2:
        sh, sw = stack2.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh, nw = sh + i, sw + j
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                    if nh == Dh and nw == Dw:
                        print(answer)
                        exit()
                    grid[nh][nw] = 1
                    stack1.append((nh, nw))
    if !stack1:
        print(-1)
        exit()

Fixed submission:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1 = [(Ch, Cw)]
stack2 = []

answer = 1

#print(grid)

while 1:
    while stack1:
        sh, sw = stack1.pop()
    
        stack2.append((sh, sw))
    
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nh, nw = sh + i, sw + j
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                if nh == Dh and nw == Dw:
                    print(answer - 1)
                    exit()
                grid[nh][nw] = answer
                stack1.append((nh, nw))
    #print(grid)
    
    if len(stack2) == 0:
        break
    
    answer += 1
    while stack2:
        sh, sw = stack2.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh, nw = sh + i, sw + j
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                    if nh == Dh and nw == Dw:
                        print(answer - 1)
                        exit()
                    grid[nh][nw] = answer
                    stack1.append((nh, nw))
    #print(grid)

print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

B = [(1000, 0)]

for a in A:
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    B = C
    
answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

B = [(1000, 0)]

for (i, a) in enumerate(A):
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    C.sort(reverse = True)

    max_rest_A = 0
    if i < N - 1: max_rest_A = max(A[i + 1:])
    
    price = 0
    temp = (0 , 0)
    for c1, c2 in C:
        if price < c1 + c2 * max_rest_A:
            price = c1 + c2 * max_rest_A
            temp = (c1, c2)
    B = [C[0], temp]

answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)

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

B = [(1000, 0)]

for a in A:
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    B = C
    
answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

B = [(1000, 0)]

for (i, a) in enumerate(A):
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    C.sort(reverse = True)

    max_rest_A = 0
    if i < N - 1: max_rest_A = max(A[i + 1:])
    
    price = 0
    temp = (0 , 0)
    for c1, c2 in C:
        if price < c1 + c2 * max_rest_A:
            price = c1 + c2 * max_rest_A
            temp = (c1, c2)
    B = [C[0], temp]

answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)
Buggy python submission (verdict: Runtime Error):
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
#N, M = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
#ABC = [list(map(int, input().split())) for _ in range(N)]

cnt = [0] * (2 * 10 ** 5 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 2 * 10 ** 5 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 2 * 10 ** 5:
        cnt[i * k] = 0
        k += 1

print(answer)
    
    
    
    
    

Fixed submission:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = [0] * (10 ** 6 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 10 ** 6 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 10 ** 6:
        cnt[i * k] = 0
        k += 1

print(answer)
Buggy python submission (verdict: Runtime Error):
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

graph = [[] for _ in range(N + 1)]
arrow = [0] * (N + 1)

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(st, graph):
    INF = 10 ** 18
    dist = [0] * len(graph)
    dist[st] = 1
    queue = deque([st])
    while queue:
        q = queue.popleft()
        for r in graph[q]:
            if dist[r] == 0:
                dist[r] = q
                queue.append(r)
    return dist

answer = bfs(1, graph)[2:]
print("Yes")
for a in answer:
    print(a)

Fixed submission:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
arrow = [0] * (N + 1)

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(st, graph):
    INF = 10 ** 18
    dist = [0] * len(graph)
    dist[st] = 1
    queue = deque([st])
    while queue:
        q = queue.popleft()
        for r in graph[q]:
            if dist[r] == 0:
                dist[r] = q
                queue.append(r)
    return dist

answer = bfs(1, graph)[2:]
print("Yes")
for a in answer:
    print(a)
Buggy python submission (verdict: Runtime Error):
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]

cnt = defaultdict(int)
zero = 0

tmp = []
for a, b in AB:
    gcd_ab = gcd(abs(a), abs(b))
    if a < 0: a,  b = - a, - b 
    tmp.append([a // gcd_ab, b // gcd_ab])
AB = tmp
#print(AB)

cnt = defaultdict(int)
zero = 0
        
for a, b in AB:
    if a * b == 0:
        zero += 1
    else:
        cnt[(a, b)] += 1
#print(cnt)

answer = 1
rest = N

answer *= zero + 1
answer %= MOD
rest -= zero

check = defaultdict(int)
for a, b in AB:
    if a > 0 and b > 0 and check[(a, b)] == 0:
        check[(a, b)] = 1
        #print((a, b), cnt[(a, b)], cnt[(b, -a)])
        answer *= pow(2, cnt[(a, b)] + cnt[(b, -a)], MOD) - (pow(2, cnt[(a, b)], MOD) - 1) * (pow(2, cnt[(b, -a)], MOD) - 1) 
        answer %= MOD
        rest -= cnt[(a, b)] + cnt[(b, -a)]

answer *= pow(2, rest, MOD)
answer -= 1
answer %= MOD

print(answer)

Fixed submission:
from sys import stdin
input = stdin.buffer.readline
from collections import defaultdict

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

MOD = 10 ** 9 + 7

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]

rest = N
zero = 0
zero_left, zero_right = 0, 0
tmp = []
for a, b in AB:
    if a == b == 0:
        zero += 1
        rest -= 1
    elif a == 0:
        zero_left += 1
    elif b == 0:
        zero_right += 1
    else:
        gcd_ab = gcd(abs(a), abs(b))
        a, b = a // gcd_ab,  b // gcd_ab
        if a < 0: a, b = -a, -b
        tmp.append([a, b])
AB = tmp

cnt = defaultdict(int)
for a, b in AB:
    cnt[(a, b)] += 1

answer = 1
answer *= pow(2, zero_left + zero_right, MOD) - (pow(2, zero_left, MOD) - 1) * (pow(2, zero_right, MOD) - 1)
answer %= MOD
rest -= zero_right + zero_left
#print("answer:", answer)

check = defaultdict(int)
for a, b in AB:
    if b > 0 and check[(a, b)] == 0:
        check[(a, b)] = 1
        answer *= pow(2, cnt[(a, b)] + cnt[(b, -a)], MOD) - (pow(2, cnt[(a, b)], MOD) - 1) * (pow(2, cnt[(b, -a)], MOD) - 1) 
        answer %= MOD
        rest -= cnt[(a, b)] + cnt[(b, -a)]

answer *= pow(2, rest, MOD)
answer += zero - 1
answer %= MOD
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for i in range(N)]

LR = []
for s in S:
    left, right = 0, 0
    for ss in s:
        if ss == "(":
            left += 1
        else:
            if left:
                left -= 1
            else:
                right += 1
    LR.append([left, right])
#print(LR)

plus = []
minus = []
for l, r in LR:
    if l >= r:
        plus.append([l, r])
    else:
        minus.append([l, r])
        
plus.sort(key = lambda x: x[1])
minus.sort(key = lambda x: -x[0])

cnt = 0
for l, r in plus + minus:
    cnt -= r
    if cnt < 0:
        print("No")
        exit()
    cnt += l
        
if cnt == 0:
    print("Yes")
else:
    print("No")

Fixed submission:
N = int(input())
S = [input() for i in range(N)]

LR = []
for s in S:
    left, right = 0, 0
    for ss in s:
        if ss == "(":
            left += 1
        else:
            if left:
                left -= 1
            else:
                right += 1
    LR.append([left, right])
#print(LR)

plus = []
minus = []
for l, r in LR:
    if l >= r:
        plus.append([l, r])
    else:
        minus.append([l, r])
        
plus.sort(key = lambda x: x[1])
minus.sort(key = lambda x: -x[0])

cnt = 0
for l, r in plus + minus:
    cnt -= r
    if cnt < 0:
        print("No")
        exit()
    cnt += l
        
if cnt == 0:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
SIZE = 10 ** 6 + 100
g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
def nPr(n, r):
    if r < 0 or r > n:
        return 0
    return g1[n] * g2[r] % MOD
def nCr(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

for i in range(A, B + 1):
    if i % K == 0:
        print("OK")
        exit()
        
print("NG")
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

def LIS(arr):
    from bisect import bisect_left
    INF = 10 ** 15
    
    len_arr = len(arr)
    LIS = [INF for i in range(len_arr + 1)]
  
    for a in arr:
      LIS_i = bisect_left(LIS, a)
      LIS[LIS_i] = min(LIS[LIS_i], a)

    for i in range(len_arr + 1):
      if LIS[i] == INF:
        return i

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
A = [0] + list(map(int, input().split()))
UV = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N + 1)]
for uv in UV:
    u, v = uv
    graph[u].append(v)
    graph[v].append(u)
#print(graph)

answer = [0] * (N + 1)
def dfs(prev, n, lst):
    answer[n] = LIS(lst)
    for g in graph[n]:
        if g != prev:
            dfs(n, g, lst + [A[g]])

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

for a in answer[1:]:
    print(a)


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

sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

def LLL(a, ls):
    INF = 10 ** 15
    
    flag = 0
    prev = 0
    indx = 0
    ls_i = bisect_left(ls, a)
    if a < ls[ls_i]:
        flag = 1
        prev = ls[ls_i]
        indx = ls_i
    ls[ls_i] = min(ls[ls_i], a)

    ls_ii = bisect_left(ls, INF)
    return ls_ii, ls, flag, prev, indx

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
A = [0] + list(map(int, input().split()))
UV = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N + 1)]
for uv in UV:
    u, v = uv
    graph[u].append(v)
    graph[v].append(u)
#print(graph)

INF = 10 ** 15

LIS = [INF for i in range(N + 2)]

answer = [0] * (N + 1)
def dfs(prev, n, LIS):
    answer[n], LIS, flag, prv, indx = LLL(A[n], LIS)
    #print(n, LIS, flag, prv, indx)
    for g in graph[n]:
        if g != prev:
            dfs(n, g, LIS)
    if flag:
        LIS[indx] = prv

dfs(-1, 1, LIS)

for a in answer[1:]:
    print(a)