Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int, input().split()))

import math
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)
ans = 0
for idx, num in enumerate(A):
  result = gcd(A[:idx:]+A[idx+1::])
  if result > ans:
    ans = result
print(ans)

### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
L = [0] * (N+1)
R = [0] * (N+2)
M = [0] * (N+1)

for i in range(1, N+1):
  L[i] = fractions.gcd(L[i-1], A[i-1])
  R[N-i+1] = fractions.gcd(R[N-i+2], A[N-i])

for i in range(1, N+1):
  M[i] = fractions.gcd(L[i-1], R[i+1])
print(max(M[1:]))
n = int(input())
N = 10**9
x = [0]*(N+1)
x1= [0]*N
x2= [0]*N
for i in range(n):
    a , b = map(int, input().split())
    x[a-1]+=1
    x[b]-=1

for i in range(1,N):
    x[i]=x[i]+x[i-1]

for i in range(1,N):
    x1[i]=x1[i]+x1[i-1]

x.reverse()
for i in range(1,N):
    s2[i]=x2[i]+x2[i-1]

ans =0
if n % 2 == 1:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans)
else:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans*2+1)


### FIXED CODE ###

n = int(input())
al=[]
bl=[]
for i in range(n):
    a , b = map(int, input().split())
    al.append(a)
    bl.append(b)
al.sort()
bl.sort()
if n%2==1:
    mi = al[n//2]
    ma = bl[n//2]
    print(int(ma-mi)+1)
else:
    mi = (al[n//2-1]+al[n//2])/2
    ma = (bl[n//2-1]+bl[n//2])/2
    print(int((ma-mi)*2+1))
N,M=input().split(' ')
dict={}
for i in range(int(M)):
  a,b=input().split(' ')
  a=int(a)
  b=int(b)
  if a not in dict:
    dict[a]=0
  dict[a]+=1
  if b not in dict:
    dict[b]=0
  dict[b]+=1
for i in range(int(N)):
  print(dict[i+1])

### FIXED CODE ###

N,M=input().split(' ')
dict={}
for i in range(int(N)):
  dict[i+1]=0
for i in range(int(M)):
  a,b=input().split(' ')
  a=int(a)
  b=int(b)
  dict[a]+=1
  dict[b]+=1
for i in range(int(N)):
  print(dict[i+1])
N = int(input())

def f(x):
    if int(x) > N:
        return 0
    else:
        if all(x.count(j) >= 1 for j in [3, 5, 7]):
            ans = 1
        for i in [3, 5, 7]:
            ans += f(x+i)    
        return ans        

print(f("0"))

### FIXED CODE ###

N = int(input())
def dfs(s):
    if int(s) > N:
        return 0
    else:
        if '7' in s and '5' in s and '3' in s:
            ret = 1
        else:
            ret = 0
        for i in '357':
            ret += dfs(s + i)
        return ret
print(dfs("0"))
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    s, w = map(int, rl().split())
    if ans = s > w :
        print('safe')
　　else:
　　    print('unsafe')
    

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    s, w = map(int, rl().split())
    if s > w:
        print('safe')
    else:
      print('unsafe')
    

if __name__ == '__main__':
    solve()
N, M, K =  [int(x) for x in input().split()]

stackA = [int(x) for x in input().split()]
stackB = [int(x) for x in input().split()]

indexB = 0
indexA = 0

books = 0
mostBooks = 0
time = 0

for x in stackB:
    if time + x > K:
        indexB -= 1
        break

    else:
        time += x
        indexB += 1
        books += 1

mostBooks = books

for x in stackA:
    time += x
    books += 1

    while time > K and indexB >= 0:
        time -= stackB[indexB]
        indexB -= 1
        books -= 1

    if indexB < 0 and time > K:
        break

    mostBooks = max(mostBooks, books)

print(mostBooks)

### FIXED CODE ###

N, M, K =  [int(x) for x in input().split()]

stackA = [int(x) for x in input().split()]
stackB = [int(x) for x in input().split()]

indexB = 0
indexA = 0

books = 0
mostBooks = 0
time = 0

for x in stackB:
    if time + x > K:
        break

    else:
        time += x
        indexB += 1
        books += 1

indexB -= 1

mostBooks = books

for x in stackA:
    time += x
    books += 1

    while time > K and indexB >= 0:
        time -= stackB[indexB]
        indexB -= 1
        books -= 1

    if indexB < 0 and time > K:
        break

    mostBooks = max(mostBooks, books)

print(mostBooks)
a, b = map(int, input().split(' '))

print("{} {} {:5f}".format(int(a/b), a%b, a/b))

### FIXED CODE ###

import math

r = float(input())

print(math.pi*(r**2), 2*math.pi*r)
N, Z, W = map(int, input().split())
a = [int(n) for n in input().split()]
b = a.pop()
max = 0
if nota == []:
    for n in a:
        if abs(n - b) > max:
            max = abs(n - b)
if abs(n - Z) > max:
    max = abs(n - Z)
if abs(n - W) > max:
    max = abs(n - W)

print(max)

### FIXED CODE ###

N, Z, W = map(int, input().split())
a = [int(n) for n in input().split()]

if N == 1:
    ans = abs(a[-1] - W)
else:
    ans = max(abs(a[-1] - W), abs(a[-1] - a[-2]))
print(ans)
N,K=map(int,input().split())
import math
s=0
for j in range(1,N+1):
  if (K/j)%2==0:
    s+=math.log2(K//j)
  else:
    s+=int(math.log2(K/j))+1
print(float(N/(s+N)))
    


### FIXED CODE ###

N,K=map(int,input().split())
i=0
q=0 #確率
for j in range(1,N+1):
  while j*(2**i)<K:
    i+=1
  q+=(1/N)*((1/2)**i)
  i=0
print(q)
a, b = map(int, input().split())
x = a + b
if x % 3 == 0:
  print('Possible')
else('Impossidle')

### FIXED CODE ###

a, b = map(int, input().split())
if (a + b) % 3 == 0 or b % 3 == 0 or a % 3 == 0:
    print("Possible")
else:
    print("Impossible")
import numpy as np
N = int(input())
As = list(map(int, input().split(' ')))
As = np.unique(np.array(As))

divisible = np.sum(np.sum((As[None]%As[:,None])==0, 0)>1)
print(divisible)

### FIXED CODE ###

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

max_a = max(a)
dp = [0] * (max_a + 1)

for i in a:
    for j in range(i, max_a+1, i):
        dp[j] += 1
        
print([dp[i] for i in a].count(1))
def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+100)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True
    try:
        if  a[x-2] != 1:
            res += (solve(x-2) % Mod)
            zeroflg = False
    except:
        pass
    try:
        if a[x-1] != 1:
            res += (solve(x-1) % Mod)
            zeroflg = False
    except:
        pass

    if zeroflg:
        return 0
    dp[x] = res
    return res


dp = [-1]*(N+100)
dp[0] = 1
dp[1] = 1

print(solve(N) % Mod)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


dp = [-1]*(N+1)
dp[0] = 1
dp[1] = 1

print(solve(N) % Mod)


'''
5 1
1
'''
import math
import functools

def lcm(a,b):
    return  int(a*b/math.gcd(a,b))
    
n=int(input())
t=[int(input()) for i in range(n)]
if n==1:
    print(t[0])
else:
    anser=1
    for i in t:
        anser=lcm(anser,i)
    print(anser)

### FIXED CODE ###

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

def lcm(a,b):
    return  a*b//gcd(a,b)
    
n=int(input())
t=[int(input()) for i in range(n)]

anser=1
for i in t:
    anser=lcm(anser,i)
print(anser)
n,x = map(int,input().split())
l = []
for i in range(n):
  l.append(int(input())
sum_l = sum(l)
mini = min(l)
rest = x - sum_l
count = n + rest//mini
print(count)

### FIXED CODE ###

n,x = map(int,input().split())
l = []
for i in range(n):
  l.append(int(input()))
sum_l = sum(l)
mini = min(l)
rest = x - sum_l
count = n + rest//mini
print(count)
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if tot > best:
            while len(c) > 1 and not is_chosen[c[0]]:
                del c[0], is_chosen[0]
            while len(c) > 1 and not is_chosen[c[-1]]:
                del c[-1], is_chosen[-1]
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in (-1, 0):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()
n = input()
h_string = input()
h_list = h_string.split(" ")
for item in h_list:
    item = int(item)


longest = 0
now_value = -1
now_length = 0


for value in h_list:
    if value <= now_value:
        now_length += 1
        now_value = value
        if now_length > longest:
            longest = now_length
    else:
        if now_length > longest:
            longest = now_length
        now_value = value
        now_length = 0

print(longest)


### FIXED CODE ###

n = input()
h_string = input()
h_list = h_string.split(" ")
for i in range(len(h_list)):
    h_list[i] =	int(h_list[i])


longest = 0
now_value = -1
now_length = 0


for value in h_list:
    if value <= now_value:
        now_length += 1
        now_value = value
        if now_length > longest:
            longest = now_length
    else:
        if now_length > longest:
            longest = now_length
        now_value = value
        now_length = 0

print(longest)
def edit_distance(M):
 n = len(M)
 A = [[0 for i in range(n)] for j in range(n)]
 for l in range(2, n+1):
  for i in range(0, n-l+1):
   k = i+l-1
   def f(i,j,k):
    return A[i][j]+A[j+1][k] + M[i][0]*M[j][1]*M[k][1]
   A[i][k] = min(f(i,j,k) for j in range(i,k))
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distace(M)

### FIXED CODE ###

def edit_distance(M):
  n = len(M)



  m = [[0 for i in range(n)] for j in range(n)]
   
  for long in range(2, n+1):

    for i in range(0, n-long+1):

      j = i + long - 1

      def a(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(a(i, k, j) for k in range(i, j))
   
  return m[0][n-1]
 
n = input()
M = []
 
for i in range(n):
  M.append(map(int, raw_input().split()))
print edit_distance(M)
#c
n,m,x=map(int, input().split())
sp = [list(map(int, input().split())) for _ in range(m)]

import copy
result = []
def test(i,i_sum,cost):
    
    flag = 0
    if i <= n:
        print(i,i_sum,cost)
        for j in range(m):
            if i_sum[j] < x:
                flag = 1
                break

        if flag == 1:
                test(copy.deepcopy(i)+1, i_sum[:],cost)#参考書を使わない場合

                for j in range(1,m+1):#参考書を使う場合
                    i_sum[j-1] += sp[i-1][j]
                cost[0] +=  sp[i-1][0]
                test(copy.deepcopy(i)+1, i_sum[:],cost)
        else:
            result.append(cost[0])
test(0,[0]*n,[0])

if result != []:
    print(min(result))
else:
    print(-1)

### FIXED CODE ###

#c
n,m,x=map(int, input().split())
sp = [list(map(int, input().split())) for _ in range(n)]

import copy
result = []
def test(i,i_sum,cost):
    
    flag = 0
    if i <= n:
        for j in range(m):
            if i_sum[j] < x:
                flag = 1
                break

        if flag == 1:
                test(copy.deepcopy(i)+1, i_sum[:],cost[:])#参考書を使わない場合

                for j in range(1,m+1):#参考書を使う場合
                    i_sum[j-1] += sp[i-1][j]
                cost[0] += sp[i-1][0]
                test(copy.deepcopy(i)+1, i_sum[:],cost[:])
        else:
            result.append(cost[0])
test(0,[0]*m,[0])

if result != []:
    print(min(result))
else:
    print(-1)
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
import sys
dxy = [(1,0),(0,1),(-1,0),(0,-1)]
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            flag = 0
            for dy,dx in dxy:
                if 0<= i+dy < W and 0 <= i+dx < H and s[i+dy][j+dx] == "#":
                    flag = 1
            if flag == 0:
                print("No")
                sys.exit(0)
print("Yes")


### FIXED CODE ###

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
import sys
dxy = [(1,0),(0,1),(-1,0),(0,-1)]
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            flag = 0
            for dy,dx in dxy:
                if 0<= i+dy < H and 0 <= j+dx < W and s[i+dy][j+dx] == "#":
                    flag = 1
            if flag == 0:
                print("No")
                sys.exit(0)
print("Yes")
N=int(input())
l=list(map(int,input().split()))
if max(l)<sum(l)-max(l):
	print("Yes")
else:
	print("NO")

### FIXED CODE ###

T,X=map(int,input().split())
print(T/X)
A, B = [int(x) for x in input().split()]

calc_res = [A+B, A-B, A*B, A/B]
print(max(calc_res))

### FIXED CODE ###

a, b = [int(x) for x in input().split()]
print(max(a+b, a-b, a*b))
a,b,c,d=map(int,input().split())
if a*b>=c*d:
    input(a*b)
else:
    input(c*d)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
print(max(a*b,c*d))
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

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

import sys
input = sys.stdin.readline
N = int(input())
T = [int(input()) for _ in range(N)]
ans = lcm(T[0], T[1])
for i in range(2, N):
    ans = lcm(ans, T[i])
print(ans)

### FIXED CODE ###

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

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

import sys
input = sys.stdin.readline
N = int(input())
if N == 1:
    print(input())
else:
    T = [int(input()) for _ in range(N)]
    ans = lcm(T[0], T[1])
    for i in range(2, N):
        ans = lcm(ans, T[i])
    print(ans)
N,Q=map(int,input().split())
dg={i:[] for i in range(1,N+1)}
for i in range(1,N):
    a,b=map(int,input().split())
    dg[a].append(b)
    dg[b].append(a)
#print(dg)
def habatan(p,me):
    if me!=1:
        dg[me].remove(p)
    for c in dg[me]:
        habatan(me,c)

habatan(0,1)#dg親消し
#print(dg)
dv={i:0 for i in range(1,N+1)}
for i in range(Q):
    p,x=map(int,input().split())
    dv[p]+=x
#dans={}
def habatan1(p,me):
    if me!=1:
        dv[me]+=dv[p]
    for c in dg[me]:
        habatan1(me,c)
habatan1(0,1)
for i in range(1,N+1):
    print(dv[i],end=" ")
print("")


### FIXED CODE ###

#import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
lp=[0]
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])
n, k = map(int, input().split())
pList = map(int, input().split())
list.sort(pList)
score = 0
for i in range(k):
    score += pList[i]
print(score)

### FIXED CODE ###

n, k = map(int, input().split())
#pList = map(int, input().split())
split = input().split()
pList = [int(i) for i in split]
list.sort(pList)
score = 0
for i in range(k):
    score += pList[i]
print(score)
n=int(input())
lst=[]
for i in range(n):
    lst.append(input())
lst=lst.sort()
print(lst)
print(lst[0])

### FIXED CODE ###

n=int(input())
lst=[]
for i in range(n):
    lst.append(input())
#lst.sort()
#print(lst)
#print(lst[0])
c="zzzzzzzzzzzzzzzzzzzzzzz"
for j in lst:
    if j < c:
        c=j
print(c)
a,b = map(int,input().split())
if(a*b<=0)print(Zero)
elif(a<0 and b-a%2==0)
	print(Positive)
else
	print(Negative)

### FIXED CODE ###

a,b = map(int,input().split())
if a*b<=0:
    print("Zero")
elif a<0 and (b-a)%2==0:
    print("Negative")
else:
    print("Positive")
from itertools import combinations_with_replacement
n=int(input())
ans=[0]*1000
list1=list(combinations_with_replacement([1,2,3,4,5,6,7,8,9,10], 3))
for i in range(len(list1)):
    x=list1[i][0]
    y=list1[i][1]
    z=list1[i][2]
    if len(list(set(list1[i])))==1:
        ans[(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z)-1]+=1
    elif len(list(set(list1[i])))==2:
        ans[(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z)-1]+=3
    else:
        ans[(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z)-1]+=6
for i in range(n):
    print(ans[i])

### FIXED CODE ###

from itertools import combinations_with_replacement
n=int(input())
ans=[0]*100000
list1=list(combinations_with_replacement(list(range(1,100)), 3))
for i in range(len(list1)):
    x=list1[i][0]
    y=list1[i][1]
    z=list1[i][2]
    if len(list(set(list1[i])))==1:
        ans[(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z)-1]+=1
    elif len(list(set(list1[i])))==2:
        ans[(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z)-1]+=3
    else:
        ans[(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z)-1]+=6
for i in range(n):
    print(ans[i])
n, k, q = map(int, input().split())
a = []
for i in range(q):
    a[i] = int(input()) - 1
score = [0 for _ in range(n)]

for a_i in a:
    score[a_i] += 1

for i in range(n):
    result = k - q + score[i]
    print("Yes" if result > 0 else "No")


### FIXED CODE ###

(n, k, q) = map(int, input().split())
a = [int(input()) for _ in range(q)]
points = [0 for _ in range(n)]

for i, answer in enumerate(a):
    points[answer-1] += 1

for i, p in enumerate(points):
    result = "Yes" if k - q + p > 0 else "No"
    print(result)
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 10**9+7


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


N = int(input())
c = [x-1 for x in map(int, input().split())]
A = [None]*(N-1)
B = [None]*(N-1)
for i in range(N-1):
    A[i], B[i] = map(int, input().split())

g = Graph(N)
for a, b in zip(A, B):
    g.add_edge(a-1, b-1)

# k=1, 2, ..., Nに対して
# 色kが塗られている頂点を一度以上通るような単純パスの数を求める
# 全パスの個数 - 色kが塗られている頂点を一度も通らない単純パスの数
# 全パスの個数はN*(N+1)/2

# グラフを色kのノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# 辞書は色iを通らずに到達可能な頂点の数を持つ。

# 辞書
reachable = [defaultdict(int) for _ in range(N)]

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        f(dest, curr)

        for color in range(N):
            n = reachable[dest][color]
            if color == c[curr]:
                # 自身の色と同じ場合、子の頂点の数から加算
                ans[color] += n*(n+1)//2
                reachable[curr][color] = 0
            else:
                # 自身の色以外については、子の情報から自分の情報を作る
                reachable[curr][color] += n
    for color in range(N):
        if color != c[curr]:
            reachable[curr][color] += 1
    return


f(0)
for color in range(N):
    if color != c[0]:
        n = reachable[0][color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
INF = float("inf")
MOD = 10**9+7


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


N = int(input())
c = [x-1 for x in map(int, input().split())]
A = [None]*(N-1)
B = [None]*(N-1)
for i in range(N-1):
    A[i], B[i] = map(int, input().split())

g = Graph(N)
for a, b in zip(A, B):
    g.add_edge(a-1, b-1)

# k=1, 2, ..., Nに対して
# 色kが塗られている頂点を一度以上通るような単純パスの数を求める
# 全パスの個数 - 色kが塗られている頂点を一度も通らない単純パスの数
# 全パスの個数はN*(N+1)/2

# グラフを色kのノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# x辞書は色iを通らずに到達可能な頂点の数を持つ。
# o辞書は色iを通らずに到達不可能な頂点の数を持つ。

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    ret = defaultdict(int)
    size = 1
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        sz, child = f(dest, curr)
        size += sz

        # 自身の色と同じ場合、子の頂点の数から加算
        n = sz-child[c[curr]]
        ans[c[curr]] += n*(n+1)//2

        # マージ
        if len(ret) < len(child):
            child, ret = ret, child
        for key in child:
            ret[key] += child[key]

    ret[c[curr]] = size
    return size, ret


sz, ret = f(0)
for color in range(N):
    if color != c[0]:
        n = sz-ret[color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)
n = int(input())
a_lis = list(map(int,input().split()))
b_lis = list(map(int,input().split()))
c_lis = list(map(int,input().split()))

s = 0

for i in range(n):
  if a_lis[i+1] - a_lis[i] == 1:
    s += c_lis[a_lis[i]]
print(sum(b_lis)+s)

### FIXED CODE ###

n = int(input())
a_lis = list(map(int,input().split()))
b_lis = list(map(int,input().split()))
c_lis = list(map(int,input().split()))
 
s = 0
 
for i in range(n-1):
  if a_lis[i+1] - a_lis[i] == 1:
    s += c_lis[a_lis[i]-1]
print(sum(b_lis)+s)
a,b,c,d=map(int,input().split())
print("Yes"if b-a<=d and c-b<=d elif c-a<=d else "No")

### FIXED CODE ###

a,b,c,d=map(int,input().split())
print("NYoe s"[(abs(b-a)<=d and abs(c-b)<=d)or abs(c-a)<=d::2])
n = input()
rem = 0
for d in n:
  rem += int(d)
if d % 9 == 0:
  print ("Yes")
else:
  print ("No")

### FIXED CODE ###

n = input()
rem = 0
for d in n:
  rem += int(d)
if rem % 9 == 0:
  print ("Yes")
else:
  print ("No")