Harryxun/stf_run huggingface dataset:
def merge( tS, left, mid, right ):
	global cnt
	n1 = mid - left;
	n2 = right - mid;
	tL = tS[ left : mid ];
	tR = tS[ mid : right ];	
	tL.append( 1000000001 )
	tR.append( 1000000001 )
	i = j = 0
	for k in range( left, right ):
		cnt += 1
		if tL[i] <= tR[j]:
			tS[k] = tL[i]
			i += 1
		else:
			tS[k] = tR[j]
			j += 1


def mergeSort( tS, left, right ):
	if left+1 < right:
		mid = ( left+right )/2
		mergeSort( tS, left, mid )
		mergeSort( tS, mid, right )
		merge( tS, left, mid, right )

n = int( input() )
arrS = [ int( val ) for val in input().split( ' ' ) ]
cnt = 0
mergeSort( arrS, 0, n )
print( " ".join( map( str, arrS ) ) )
print( cnt )

### FIXED CODE ###

def merge( tS, left, mid, right ):
	global cnt
	n1 = mid - left;
	n2 = right - mid;
	tL = tS[ left : mid ];
	tR = tS[ mid : right ];	
	tL.append( 1000000001 )
	tR.append( 1000000001 )
	i = j = 0
	for k in range( left, right ):
		cnt += 1
		if tL[i] <= tR[j]:
			tS[k] = tL[i]
			i += 1
		else:
			tS[k] = tR[j]
			j += 1


def mergeSort( tS, left, right ):
	if left+1 < right:
		mid = ( left+right )//2
		mergeSort( tS, left, mid )
		mergeSort( tS, mid, right )
		merge( tS, left, mid, right )

n = int( input() )
arrS = [ int( val ) for val in input().split( ' ' ) ]
cnt = 0
mergeSort( arrS, 0, n )
print( " ".join( map( str, arrS ) ) )
print( cnt )
# -*- coding: utf-8 -*-
o = list(input())
e = list(input())

len_o = len(o)
len_e = len(e)

if len_o == len_e:
    for i in range(len_o - 1):
        print(o[i], end = '')
        print(e[i], end = '')
    print(o[len_o - 1], end = '')
    print(e[len_e - 1])

else:
    for i in range(min(len_o, len_e):
        print(o[i], end = '')
        print(e[i], end = '')
    if len_e > len_o:
        print(e[len(e) - 1])
    if len_o > len_e:
        print(o[len(o) - 1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
o = list(input())
e = list(input())

len_o = len(o)
len_e = len(e)

if len_o == len_e:
    for i in range(len_o - 1):
        print(o[i], end = '')
        print(e[i], end = '')
    print(o[len_o - 1], end = '')
    print(e[len_e - 1])

else:
    for i in range(min(len_o, len_e)):
        print(o[i], end = '')
        print(e[i], end = '')
    if len_e > len_o:
        print(e[len(e) - 1])
    if len_o > len_e:
        print(o[len(o) - 1])
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = (set(), set())
    visited[0].add(s)
    visited[1].add(t)

    def remember(visited, new):
        g[new] |= visited
        for v in visited:
            g[v].add(new)
        visited[new] = 1

    while queue:
        st, i = queue.popleft()
        for f in g[i]:
            if visited[not st][f]:
                return True
            if not visited[st][f]:
                remember(visited[st], f)
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
s = input()
sa = s.replace('LR','L,R')
sb = sa.split(',')
ans = ''
for hoge in sb:
  poge = len(sb)
  g = hoge.find('RL')
  if poge%2 == 0:
    r = poge//2
    l = poge//2
  else:
    if g%2 == 0:
      r = poge//2
      l = r + 1
    else:
      l = poge//2
      r = l + 1
  an = '0 '*(g-1)+str(r)+' '+str(l)+' 0'*(poge-g-1)+ ' '
  ans += an
print(ans)

### FIXED CODE ###

s = input()
sa = s.replace('LR','L,R')
sb = sa.split(',')
ans = ''
for hoge in sb:
  poge = len(hoge)
  g = hoge.find('RL')
  if poge%2 == 0:
    r = poge//2
    l = poge//2
  else:
    if g%2 == 1:
      r = poge//2
      l = r + 1
    else:
      l = poge//2
      r = l + 1
  an = '0 '*(g)+str(r)+' '+str(l)+' 0'*(poge-g-2)+ ' '
  ans += an
print(ans)
n=int(input())
a=list(map(int,input().split()))
b=[0]*9
for i in range(n):
  if a[i]<400:
    b[0]+=1
  elif a[i]<800:
    b[1]+=1
  elif a[i]<1200:
    b[2]+=1
  elif a[i]<1600:
    b[3]+=1
  elif a[i]<2000:
    b[4]+=1
  elif a[i]<2400:
    b[5]+=1
  elif a[i]<2800:
    b[6]+=1
  elif a[i]<3200:
    b[7]+=1
  else:
    b[8]+=1
    
min=8-b[:8].count(0)
max=min+b[8]

if min=0:
  min=1
print(min,max)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*9
for i in range(n):
  if a[i]<400:
    b[0]+=1
  elif a[i]<800:
    b[1]+=1
  elif a[i]<1200:
    b[2]+=1
  elif a[i]<1600:
    b[3]+=1
  elif a[i]<2000:
    b[4]+=1
  elif a[i]<2400:
    b[5]+=1
  elif a[i]<2800:
    b[6]+=1
  elif a[i]<3200:
    b[7]+=1
  else:
    b[8]+=1
    
min=8-b[:8].count(0)
max=min+b[8]

if min==0:
  min=1
print(min,max)
import math
listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
        #または、quit(),os.exit()をして止める。

a = listA[0][0]
b = listA[0][1]
n = listA[0][2]

old = 0
for x in range(1,n+1):
  if x == 1:
    c = math.floor((a*x)/b)
    d = math.floor(x/b)
    old = c-(a*d)
  else:
    c = math.floor((a*x)/b)
    d = math.floor(x/b)
    current = c-(a*d)
    if old <= current:
      old = current
  if x > 10000000:
    break
print (old)
  


### FIXED CODE ###

listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
        #または、quit(),os.exit()をして止める。

a = listA[0][0]
b = listA[1][0]
c = listA[1][1]

if b % a == 0:
  print ('OK')

d = b // a

if b % a !=0:
  if a * (d+1) <= c:
    print ('OK')
  else:
    print ('NG')
import math
def main():
    def get_inputs():
        input_list = []
        count = 0
        try:
            while count < 50:
                input_list.append(input())
                count += 1
        except EOFError:
            return input_list

    input_list = get_inputs()
    lcm = lambda a,b: a*b / math.gcd(a,b)
    for str_num in input_list:
        tmp = str_num.split(" ")
        a,b = int(tmp[0]),int(tmp[1])
        x = math.gcd(a,b)
        y = int(lcm(a,b))
        print("{} {}".format(x,y))
    return None


if __name__ == '__main__':
    main()

### 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)


while True:
    try:
        a, b = [int(i) for i in input().split()]
        print(gcd(a, b), lcm(a, b))
    except EOFError:
        break
I = int(input().split())
if I[0] < I[1]:
    print("a < b")
if I[0] > I[1]:
    print("a > b")
if I[0] == I[1]:
    print("a == b")

### FIXED CODE ###

I = input().split()
if int(I[0]) < int(I[1]):
    print("a < b")
if int(I[0]) > int(I[1]):
    print("a > b")
if int(I[0]) == int(I[1]):
    print("a == b")
N = int(input())
S = input()
if N%2 == 0:
  if S[:N//2+1] == [N//2:]:
    print("Yes")
  else:
    print("No")
else:
  print("No")

### FIXED CODE ###

N = int(input())
S = input()
if N%2 == 0:
  if S[:N//2] == S[N//2:]:
    print("Yes")
  else:
    print("No")
else:
  print("No")
N,M = map(int,input().split())
print(N * (N -1) //　2 + M * (M - 1) // 2)


### FIXED CODE ###

N,M = map(int,input().split())
print(N*(N-1)//2+M*(M-1)//2)
int(A)
int(N)
if N%500<=A:
  print ("Yes")
else:
  print("No")

### FIXED CODE ###

a = int(input())
n = int(input())
if((a%500)<=n):
  print("Yes")
else:
  print("No")
s = input()
n = len(s) - 1
for i in range(2**n):
    tmp = []
    for j in range(n):
        tmp.append(s[i])
        if i >> j & 1:
            tmp.append("+")
        else:
            tmp.append("-")
    tmp.append(s[-1])
    for k in tmp:
        if eval(k) == 7:
            print(k + "=7")

### FIXED CODE ###

s = input()
n = len(s)
for i in range(2**(n-1)):
    op = ["-"] * (n-1)
    for j in range(n-1):
        if (i >> j) & 1:
            op[n - 2 -j] = "+"
    #print(op)
    chk = ""
    for p_n, p_o in zip(s, op + [""]):
        chk += (p_n + p_o)
    if eval(chk) == 7:
        print(chk + "=7")
        exit()
K,X=map(int,input().split())
for i in range (X-K+1,X+K-1)
    print(i)

### FIXED CODE ###

K,X=map(int,input().split())
for i in range (X-K+1,X+K):
    print(i)
A,B = map(int,input())
ans = 0
for n in range(A,B+1):
  s = str(A)
  if s == s[::-1]: ans += 1
print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
ans = 0
for n in range(A,B+1):
  s = str(n)
  if s == s[::-1]: ans += 1
print(ans)
import sys
sys.setrecursionlimit(10000)

def rec(i,j,k):
    if k == N or i == N - 1 or j == N - 1:
        return
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - i)
    dp[i+1][j] = tmp if tmp > dp[i+1][j] else dp[i+1][j]
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - N + j + 1)
    dp[i][j+1] = tmp if tmp > dp[i][j+1] else dp[i][j+1]
    rec(i + 1, j, k + 1)
    rec(i, j + 1, k + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

dp = [[0 for _ in range(N)] for _ in range(N)]
rec(0, 0, 0)
ans = -1
for i in range(4):
    for j in range(4):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]
d = deque([(0,0)])
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
while(len(d)>0):
    i, j = d.pop()
    if i + j > N - 1:
        continue
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        if dp[i+1][j] == 0:
            d.appendleft((i+1,j))
        dp[i+1][j] = tmp
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp > dp[i][j+1]:
        if dp[i][j+1] == 0:
            d.appendleft((i,j+1))
        dp[i][j+1] = tmp
        
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)
a = input()
b = int(a)
c = list(a)
t = int(a[0])
#print(t,a.count("9"))
if t != 9  and a.count("9") == len(a)-1:
    r = t+(len(a)-1)*9
elif a.count("9") != len(a):
    t -= 1
    r = t+(len(a)-1)*9
if b<9:
    r = b
elif b == 9:
    r = 9
    
print(r)

### FIXED CODE ###

a = input()
b = int(a)
c = list(a)
t = int(a[0])
r = t+(len(a)-1)*9
#print(t,a.count("9"))
if t != 9  and a.count("9") == len(a)-1:
    r = t+(len(a)-1)*9
elif a.count("9") != len(a):
    t -= 1
    r = t+(len(a)-1)*9
if b<9:
    r = b
elif b == 9:
    r = 9
    
print(r)
import sys
input = sys.stdin.readline

from collections import deque

N = int(input())

# empty
N -= 1

if N == 0:
    print(1)
    print(1,1)
    exit()

bit = [i for i in range(60) if N&(1<<i)]

n = bit[-1]
left = deque(range(n,0,-1))
right = deque()
x = n+1

for i in range(n,0,-1):
    right.append(i)
    if i-1 in bit:
        right.append(x)
        left.appendleft(x)
        x += 1

S = left + right
print(len(S))
print(' '.join(map(str,S)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())

# empty
N += 1

bit = [i for i in range(60) if N&(1<<i)]

n = bit[-1]
left = deque(range(n,0,-1))
right = deque()
x = n+1

for i in range(n,0,-1):
    right.append(i)
    if i-1 in bit:
        right.append(x)
        left.appendleft(x)
        x += 1

S = list(left) + list(right)
print(len(S))
print(' '.join(map(str,S)))
N,M=map(int,input().split())
#N=3
#M=7

MEMO=[[0]*(2) for i in range(N+1)]
MEMO[0][0]=1
MEMO[0][1]=1

for i in range (1,N+1):
    MEMO[i][0]=MEMO[i-1][0]*2+3
    MEMO[i][1]=MEMO[i-1][1]*2+1
t=1
s=0
n=N-1
while(True):
        if(t==M):break
        if(t+MEMO[n][0]<M):
            if f==0:
                t=t+MEMO[n][0]+1
                s+=MEMO[n][1]+1
                f+=1
            else:
                s+=MEMO[n][1]
                break
        elif(t+MEMO[n][0]>M):
            t+=1
            n-=1
            f=0
        else:
            s+=MEMO[n][1]
            break
print(s)

### FIXED CODE ###

N,M=map(int,input().split())
#N=3
#M=7

MEMO=[[0]*(2) for i in range(N+1)]
MEMO[0][0]=1
MEMO[0][1]=1

for i in range (1,N+1):
    MEMO[i][0]=MEMO[i-1][0]*2+3
    MEMO[i][1]=MEMO[i-1][1]*2+1
t=1
s=0
n=N-1
f=0
while(True):
        if(t==M):break
        if(t+MEMO[n][0]<M):
            if f==0:
                t=t+MEMO[n][0]+1
                s+=MEMO[n][1]+1
                f+=1
            else:
                s+=MEMO[n][1]
                break
        elif(t+MEMO[n][0]>M):
            t+=1
            n-=1
            f=0
        else:
            s+=MEMO[n][1]
            break
print(s)
a,b,c = map(int, input().split())

if a+b+c==0:
  print(0)
elif a+b+c==1:
  print(1)
elif a+b+c==2:
  print(2)
elif a+b+c==3:
  print(3)

### FIXED CODE ###

a = str(input())
print(a.count('1'))
S =input()

input_line = int(input())

flag0 = ""
flag1 = ""
flag = 0


for i in range(input_line):
    action = list(input())
    # print(flag0,flag1)
    # print(action)
    if action[0]=="1":
        if flag == 0:
            flag = 1
        else:
            flag = 0
    else:
        # print("check")
        if action[2] == "2":
            
            if flag == 0:
                flag0 = flag0 + action[4]
            elif flag ==1:
                flag1 = action[4] + flag1
        else:
            if flag == 0:
                flag0 = action[4] + flag0
            
            elif flag == 1:
                flag1 += action[4]
                
S = flag0 + S + flag1
if flag == 1:
    S = S[::-1]
    
print(S)

### FIXED CODE ###

Line = set(list(input()))

if len(Line) == 2:
    print("Yes")
else:
    print("No")
a=[]
while True:
 n=input()
 if int(n)==0:break
 a.append(n)
for s in a:
 x,y=s.split()
 if x>y:print(f'{y} < x')
 else:print(s)

### FIXED CODE ###

import sys
for s in sys.stdin:
 if'0 0\n'==s:break
 print(*sorted(map(int,s.split())))
import numpy as np

n,m = input().split(" ")
n = int(n)
m = int(m)

H = input().split(" ")
H = np.array([int(h) for h in H])

M = np.zeros((n,n))
for i in range(m):
    a, b = input().split(" ")
    M[int(a)-1, int(b)-1] = 1
    M[int(b)-1, int(a)-1] = 1

G = []
for i in range(n):
    if sum(M[i, :]==1)==0:
        G += [i]
    else:
        if (np.max(H[M[i,:]==1]) < H[i]):
            G+= [i]

print(len(G))


### FIXED CODE ###

import numpy as np
 
n,m = input().split(" ")
n = int(n)
m = int(m)
 
H = input().split(" ")
H = np.array([int(h) for h in H])
Hs = np.zeros(n)

for i in range(m):
    a, b = input().split(" ")
    a = int(a) - 1
    b = int(b) - 1
    Hs[a] = np.max([Hs[a], H[b]])
    Hs[b] = np.max([Hs[b], H[a]])
 
G = []
for i in range(n):
    if Hs[i] < H[i]:
        G += [i]
 
print(len(G))
def bfs(linkL, chckL, nextNL, breath):
    pasNL = []
    for item in nextNL:
        for lnkItem in linkL[item]:
            linkL[lnkItem].remove(item)
            if chckL[lnkItem] == -1:
                chckL[lnkItem] = breath+1
                pasNL.append(lnkItem)
        linkL[item] = []

    if len(pasNL) == 0:
        return chckL
    else:
        chckL = bfs(linkL, chckL, pasNL, breath+1)
        return chckL


import copy

N, X, Y = map(int, input().split())
mySum = [0] * (N-1)

lList = []

for indx in range(N):
    tmpList = []
    if indx != 0:   tmpList.append(indx-1)
    if indx != N-1: tmpList.append(indx+1)
    if indx == X-1: tmpList.append(Y-1)
    if indx == Y-1: tmpList.append(X-1)
    lList.append(tmpList)


for baseIndx in range(N):
    tmpLink = copy.deepcopy(lList)

    chckList = [-1] * N

    chckList[baseIndx] = 0

    chckList = bfs(tmpLink, chckList, [baseIndx], 0)
    chckList = chckList[baseIndx+1:N]

    for sumIndx in range(N-1):
        mySum[sumIndx] += chckList.count(sumIndx+1)

for printIndx in range(N-1):
    print(mySum[printIndx])


### FIXED CODE ###

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

X = X-1
Y = Y-1

kDict = {}

for kIndx in range(1, N+1):
    kDict[kIndx] = 0

for jIndx in range(N):
    for iIndx in range(jIndx):
        if (jIndx <= X) or (iIndx >= Y):
            kDict[jIndx - iIndx] += 1
        elif (iIndx <= X) and (jIndx >= Y):
            kDict[(jIndx - iIndx) - (Y - X - 1)] += 1
        elif (iIndx <= X) and ((jIndx > X) and (jIndx < Y)):
            if 2 * jIndx - (X + Y) - 1 > 0:
                kDict[(jIndx - iIndx) - (2 * jIndx - (X + Y) - 1)] += 1
            else:
                kDict[jIndx - iIndx] += 1
        elif ((iIndx > X) and (iIndx < Y)) and (jIndx >= Y):
            if (X + Y) - 2 * iIndx - 1 > 0:
                kDict[(jIndx - iIndx) - ((X + Y) - 2 * iIndx - 1)] += 1
            else:
                kDict[jIndx - iIndx] += 1
        else:
            if (2 * (jIndx - iIndx) - (Y - X) - 1) > 0:
                kDict[(jIndx - iIndx) - (2 * (jIndx - iIndx) - (Y - X) - 1)] += 1
            else:
                kDict[jIndx - iIndx] += 1

for kIndx in range(1, N):
    print(kDict[kIndx])
'AC x',str(count_AC)\n'WA x',str(count_WA)\n'TLE x',str(count_TLE)\n'RE x',str(count_RE)

### FIXED CODE ###

num=int(input())
count_AC=0
count_WA=0
count_TLE=0
count_RE=0

def judge(x):
        global count_AC
        global count_WA
        global count_TLE
        global count_RE
        if x=='AC':
            count_AC+=1
        if x=='WA':
            count_WA+=1
        if x=='TLE':
            count_TLE+=1
        if x=='RE':
            count_RE+=1

for i in range(num):
        judge(input())

print('AC x',str(count_AC),'\nWA x',str(count_WA),'\nTLE x',str(count_TLE),'\nRE x',str(count_RE))
a,b=map(int,input().split())
if len(a)==1 and len(b)==1:
  print(a*b)
else:
  print(-1)

### FIXED CODE ###

a,b=map(str,input().split())
if len(a)==1 and len(b)==1:
  print(int(a)*int(b))
else:
  print(-1)
s =input()
n = len(s)+1
k = int(input())

for i in range(n):
    if s[i] == '1':
        continue
    else:
        print(int(s[i]))
        break
else:
    print(1)


### FIXED CODE ###

s =input()
n = len(s)
k = int(input())

for i in range(k):
    if s[i] == '1':
        continue
    else:
        print(int(s[i]))
        break
else:
    print(1)
N = int(input())
n = input()    
m = n.split()
p = [int(i) for i in m]
j = 1
for i in range(N):
    if p[i] == j:
        j = j+1
if j = 1:
    print("-1")
else:
    print(N - j + 1)

### FIXED CODE ###

N = int(input())
n = input()    
m = n.split()
p = [int(i) for i in m]
j = 1
for i in range(N):
    if p[i] == j:
        j = j+1
if j == 1:
    print("-1")
else:
    print(N - j + 1)
x = input().split()
i = map(int,x)
a = i[0]
b = i[1]

if a < b:
  print('a < b')
elif a == b:
  print('a == b')
else:
  print('a > b')

### FIXED CODE ###

x = input().split()
i = list(map(int,x))
a = i[0]
b = i[1]

if a > b:
  print('a > b')
elif a == b:
  print('a == b')
else:
  print('a < b')
MOD = 10**9+7

n = int(input())

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


dic = {}

ind = [0 for i in range(n+1)]

for i in range(1,n+1):
    c = int(input())
    if c in dic:
        ind[i] = dic[c][-1]
        dic[c].append(i)
    else:
        dic[c] = [i]

dp[0] , dp[1],dp[2] = 1,1,1

for i in range(3,n+1):
    dp[i] = (dp[i] + dp[i-1]) % MOD
    if(ind[i] == 0):continue
    if(ind[i] == i-1):continue
    dp[i] = (dp[i] + dp[ind[i]]) % MOD

print(dp[n])

### FIXED CODE ###

MOD = 10**9+7

n = int(input())

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

if(n == 1):
    print("1")
    exit()
if(n==2):
    print("1")
    exit()

dic = {}

ind = [0 for i in range(n+1)]

for i in range(1,n+1):
    c = int(input())
    if c in dic:
        ind[i] = dic[c][-1]
        dic[c].append(i)
    else:
        dic[c] = [i]

dp[0] , dp[1],dp[2] = 1,1,1

for i in range(3,n+1):
    dp[i] = (dp[i] + dp[i-1]) % MOD
    if(ind[i] == 0):continue
    if(ind[i] == i-1):continue
    dp[i] = (dp[i] + dp[ind[i]]) % MOD

print(dp[n])
def is_prime(x, i):
  if i*i > x:
    return True
  elif x % i == 0:
    return False
  else:
    is_prime(x, i+1)
  
def gen_prime(x):
  if is_prime(x, 2):
    return x
  else:
    gen_prime(x+1)
    
if __name__ == "__main__":
  x = int(input())
  print(gen_prime(x))

### FIXED CODE ###

def is_prime(x, i):
  if i*i > x:
    return True
  elif x % i == 0:
    return False
  else:
    return is_prime(x, i+1)
  
def gen_prime(x):
  if is_prime(x, 2):
    return x
  else:
    return gen_prime(x+1)
    
if __name__ == "__main__":
  import sys
  sys.setrecursionlimit(10240)
  x = int(input())
  print(gen_prime(x))
import sys
sys.setrecursionlimit(2*10**5)

N = int(input())  # 頂点数
C = [int(x) - 1  for x in input().split()]  # 頂点の色番号 (1~N) -> (0~N-1)

E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

# 区間データを保管するテーブル
class BIT():
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)  # 今回は1で初期化する。 BIT の先頭は 1からなのでずらす
        
    def add(self, i, s):  # i の情報を更新する
        while i <= self.size:
            self.data[i] += s
            i += i & -i
    
    def sum(self, i):  # 1～i 番目までの合計
        tmp = 0
        while i > 0:
            tmp += self.data[i]
            i -= i & -i
        return tmp

def dfs(u, p = -1):

    global k, I, O
    
    us = 1
    I[u] = k
    k += 1
    
    for v in E[u]:
        if not v == p:
            us += dfs(v, u)
    O[u] = k

    return us

# 経路の組み合わせ数を計算する
def comb2(n):
    return n*(n+1)//2

k = 1
I = [0] * N  # 走査に入ったタイミング
O = [0] * N  # 上に戻ったタイミング
dfs(0)

# 色番号ごとに、頂点をまとめる。まとめらたら、子要素から操作するように並べ替える
VC = [ [] for _ in range(N)]
for j in range(N):
    VC[C[j]].append(j)

for j in range(N):
    VC[j].sort(key=lambda x:I[x], reverse=True)


total = comb2(N)

bit = BIT(N)
for i in range(N):
    bit.add(i+1, 1)

for j in range(N):
        
    ans = total
    history = []
    for u in VC[j]:
        cnt = 1
        for v in E[u]:
            if I[u] > I[v]:
                continue
            num = bit.sum(O[v]-1) - bit.sum(I[v]-1)
            ans -= comb2(num)
            cnt += num
        bit.add(I[u], -cnt)
        history.append((I[u], cnt))
    ans -= comb2(bit.sum(N))
    for a, b in history:
        bit.add(a,b)
    print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
 
N = int(input())  # 頂点数
C = [int(x) - 1  for x in input().split()]  # 頂点の色番号 (1~N) -> (0~N-1)
 
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    
def dfs(u, p = -1):
 
    color = C[u]  # 色番号
    VC[color].append(u)  # 色ごとに stack しておく
    
    s = 1  # 部分木サイズ（を格納する）
    for v in E[u]:
        if v == p:
            continue
            
        child[u] = 0  # v の方向にある子孫のうち辿れる頂点の数 = s - 子孫にある、同色を根とする部分木のサイズの合計
        ret = dfs(v, u)
 
        s += ret  # 純粋な部分木のサイズを計算
        child[u] += ret  # 同色の頂点が切り離されたあとの部分木サイズ
        
        ans[color] -= child[u] * (child[u] + 1) // 2        
 
    VC[color].pop()
    if VC[color]: # 上位に同じ色がある場合
        child[VC[color][-1]] -= s  # 一番近い同色から、自分の部分木の大きさをひく
    else:  # 上位に同じ色がない場合
        root_size[color] -= s  # 上位に残っている頂点の数
        
    return s

child = [0] * N  # 辿っている子の中でのの残り数　とりあえず 0で初期化
root_size = [N] * N  # 根方向に残っている頂点の数（を格納する。操作前は N 全部）
VC = [ [] for _ in range(N)]  # 色番号ごと
ans = [N*(N+1)//2] * N  # 色ごとの（残りの）組み合わせ数　初期値は 全点の組み合わせ
 
dfs(0)
 
for i in range(N):
    print(ans[i] - root_size[i] * (root_size[i] + 1) // 2)