Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

class Node:
    def __init__(self, id):
        self.id = id
        self.value = 0
        self.children = []
    
    def spread(self):
        if len(self.children)==0:
            return
        
        for child in self.children:
            child.value += self.value
            child.spread()
        

n, q = map(int, input().split())

edges = [tuple(map(int, input().split())) for _ in range(n-1)]
nodedict = dict()
root = Node(1)
nodedict[root.id] = root

marked = [root.id]
while len(edges) > 0:
    tmp = []
    rm = []
    for i, edge in enumerate(edges):
        if edge[0] in marked:
            new = Node(edge[1])
            nodedict[edge[1]] = new
            nodedict[edge[0]].children.append(new)
            rm.append(edge)
            tmp.append(edge[1])
        elif edge[1] in marked:
            new = Node(edge[0])
            nodedict[edge[0]] = new
            nodedict[edge[1]].children.append(new)
            rm.append(edge)
            tmp.append(edge[0])
    marked = tmp
    for r in rm:
      edges.remove(r)

for _ in range(q):
    p, x = map(int, input().split())
    nodedict[p].value += x

root.spread()

print(' '.join([str(nodedict[i].value) for i in range(1, n+1)]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N, Q = map(int, input().split())

nodes = [[] for _ in range(N)]
values = [0 for _ in range(N)]

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

for _ in range(Q):
  p, x = map(int, input().split())
  p = p-1
  values[p] += x

def dfs(i, p):
  for c in nodes[i]:
    if c != p:
      values[c] += values[i]
      dfs(c, i)

dfs(0, None)
print(*values)
### BUGGY CODE ###

import collections as col
n = int(input())
a = list(map(int,input().split()))
cnt = col.Counter(a)

ans = 0
for key,val in cnt.items(): ans += val*(val-1)//2

for i in range(n):
    print(ans - a.count(a[i]) + 1)



### FIXED CODE ###

import collections as col
n = int(input())
a = list(map(int,input().split()))
cnt = col.Counter(a)

ans = 0
for key,val in cnt.items(): ans += val*(val-1)//2

for i in range(n):
    print(ans - cnt[a[i]] + 1)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(remain):
    if remain == 1:
        return ['a']
    arr = [chr(ord('a') + i) for i in range(remain)]
    tmp = func(remain - 1)
    res = []
    for i in range(remain):
        res.extend(deepcopy(tmp))
        for j in range(i * len(tmp), (i + 1) * len(tmp)):
            if len(set(res[j])) < i:
                continue
            res[j] += arr[i]
    i = 0
    while i < len(res):
        if len(res[i]) < remain:
            del res[i]
        else:
            i += 1
    return res

n = INT()
ans = func(n)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(remain):
    if remain == 1:
        return ['a']
    arr = [chr(ord('a') + i) for i in range(remain)]
    tmp = func(remain - 1)
    res = []
    for i in range(remain):
        res.extend(deepcopy(tmp))
        for j in range(i * len(tmp), (i + 1) * len(tmp)):
            if len(set(res[j])) < i:
                continue
            res[j] += arr[i]
    i = 0
    while i < len(res):
        if len(res[i]) < remain:
            del res[i]
        else:
            i += 1
    return res

n = INT()
ans = func(n)
ans.sort()
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=sorted(lmp())
b=[0]*n
for i in range(n):
    if i>=1:
        if a[i]==a[i-1]:
            b[i-1]=1
    if b[i]==0:
        x=a[i]
        for k in range(i+1,n):
            if b[k]==0:
                if a[k]%x==0:
                    b[k]=1

print(b.count(0))

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

M=10**6+10
n=int(input())
a=Counter(lmp()).most_common()
a=sorted(a, key=lambda x: x[0])
c=[0]*M
for j,x in a:
    if c[j]==0:
        k=2
        while j*k<M:
            c[j*k]=1
            k+=1
ans=0
for x,y in a:
    if c[x]==0 and y==1:
        ans+=1
print(ans)
### BUGGY CODE ###

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)]
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(H*W,0,-1):
  if i+D<=H*W:g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
  for j in range(H*W//D,1,-1):
    if i+D*j<=H*W:g[i][i+D*j]=g[i+D][i+D*j]+g[i][i+D]
for q in range(Q):
  l,r=map(int,input().split());print(g[l][r])

### FIXED CODE ###

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
        for j in  range(i+1, n):
                ans  += (a[i] * a[j]) %((10**9) + 7)
                ans  = ans % ((10**9) + 7)
print(ans)

### FIXED CODE ###

d = 1000000007
n = int(input())
a = list(map(int, input().split()))
summation = sum(a)
diagonal = 0
for i in range(len(a)):
        diagonal += a[i] ** 2 
ans = (((summation  ** 2) - diagonal) // 2) % d
print(ans)
### BUGGY CODE ###

inf = 10**10
H, N = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for n in range(N):
    for h in range(H):
        if dp[h] == inf:
            continue
        dp[h + A[n]] = min(dp[h + A[n]], dp[h] + B[n])
print(min(dp[H:]))


### FIXED CODE ###

inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()
### BUGGY CODE ###

import collections

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
c = collections.Counter(A)

if (K - Q) > 0:
    for _ in range(N):
        print('Yes')
else:
    l = []
    for i,v in dict(c).items():
        if v >(Q - K):
            l.append(i-1)
    l.sort()
    for j in range(N):
        if j in l:
            print('Yes')
            l.pop(0)
        else:
            print('No')

### FIXED CODE ###

import collections

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
c = collections.Counter(A)

if (K - Q) > 0:
    for _ in range(N):
        print('Yes')
else:
    l = ['No'] * N
    for i,v in dict(c).items():
        if v >(Q - K):
            l[i-1] = 'Yes'
    for j in l:
        print(j)
### BUGGY CODE ###

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L, reverse=True)

    ans = 0
    for i in range(N):
        tmp = 0
        count = 0

        for j in range((i+1), N):
            if L[i]/2 >= L[j]:
                break
            elif L[i] == L[j]:
                tmp += len(L[j+1::])
                count += 1
                continue
            elif L[i] != L[j]:
                ans += tmp*count

            #for k in range((j+1), N):
            #    if L[i] < (L[j]+L[k]):
            #        ans += 1

                ans += len([t for t in L[j+1::] if L[i] < (L[j]+t)])





    
    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L)
    
    ans = 0
    for i in range(N-1):
        for j in range((i+1), N):    
            c = bisect.bisect_left(L, L[i] + L[j], j+1)
            ans += c - j - 1

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, m = map(int, input().split())
cnt = [0]  * n
for i in range(m):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        cnt[j - 1] += 1

print(cnt.count(m))

### FIXED CODE ###

n, m = map(int, input().split())
l = []
r = []
for i in range(m):
    L, R = map(int, input().split())
    l.append(L)
    r.append(R)
L1 = max(l)
R1 = min(r)
if R1 >= L1:
    print(R1 - L1 + 1)
else:
    print(0)
### BUGGY CODE ###

def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi1 = dp[i + 1]
    for j in range(tlen):
      if s[i] == t[j]:
        dpi1[j + 1] = max(dpi1[j + 1], dp[i][j] + 1, dpi1[j], dp[i][j + 1])
      else:
        dpi1[j + 1] = max(dpi1[j + 1], dpi1[j], dp[i][j + 1])
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

# if the remainders (mod 2019) are equal, the difference will be divisible
# x = Q*2019+5 y = R*2019+5 then x-y=(Q-R)*2019
# unless Q-R<=0
# where the substring itself is (Q-R)*2019/10**(something)
# 2019 = 3*673 in prime factorization
# so multiplying by 10 doesn't affect whether a number is divisible by it
from collections import Counter
s = input()[::-1]
partial = 0
remainders = list()
for i, character in enumerate(s):
  partial = (partial+int(character)*10**i)%2019
  remainders.append(partial)
histo = Counter(remainders)
non_single_count = int(sum(count*(count-1)/2 for value, count in histo.items() if value!=0))
single_count = int(sum(count for value, count in histo.items() if value==0))
print(non_single_count+single_count)

### FIXED CODE ###

# if the remainders (mod 2019) are equal, the difference will be divisible
# x = Q*2019+5 y = R*2019+5 then x-y=(Q-R)*2019
# unless Q-R<=0
# where the substring itself is (Q-R)*2019/10**(something)
from collections import Counter
s = input()[::-1]
partial = 0
remainders = list()
num = (int(character) for character in s)
for i, int_char in enumerate(num):
  partial = (partial+(int_char*pow(10,i,2019))%2019)%2019
  remainders.append(partial)
histo = Counter(remainders)
non_single_count = int(sum(count*(count-1)/2 for value, count in histo.items() if value!=0))
single_count = int(sum(count+count*(count-1)/2 for value, count in histo.items() if value==0))
print(non_single_count+single_count)
### BUGGY CODE ###

from collections import deque

N,M = [int(x) for x in input().split()]
next =[set() for _ in range(N+1)]

for i in range(M):
    A,B = [int(x) for x in input().split()]
    next[A].add(B)
    next[B].add(A)

opened = deque()
opened.append(1)

#closed = set()
closed = [False] * (N+1)
prev = [-1] * (N+1)
prevlen = [float('inf')] * (N+1)
prevlen[1] = 0

while len(opened) != 0:
    target = opened.popleft()
    #closed.add(target)
    closed[target] = True
    for n in next[target]:
        # if n not in closed:
        if closed[n] == False:
            opened.append(n)
        if prevlen[n] > prevlen[target]+1:
            prev[n] = target
            prevlen[n] = prevlen[target]+1


print('Yes')
for i in range(2,N+1):
    print(prev[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
from collections import deque

N,M = [int(x) for x in input().split()]
next =[set() for _ in range(N+1)]

for i in range(M):
    A,B = [int(x) for x in input().split()]
    next[A].add(B)
    next[B].add(A)

opened = deque()
opened.append(1)

prev = [-1] * (N+1)
prev[1] = 1

while len(opened) != 0:
    target = opened.popleft()
    for n in next[target]:
        if prev[n] == -1:
            opened.append(n)
            prev[n] = target


print('Yes')
# for i in range(2,N+1):
#     print(prev[i])
print(" ".join([str(x) for x in prev[2:]]))
### BUGGY CODE ###

def g(i, left):
    if left <= 0: return None
    ret = set()
    for j in range(i, n+1):
        r = g(j+1, left)
        if r: ret |= r
        r = g(j+1, left-j)
        if r: ret |= set((j,) + x for x in r)
        if j == left: ret |= {(j,),}
    return ret

def f(s, i, d):
    left = s - sum(d.get(i, [0]))
    if left < 0: return None
    if left == 0: return d
    for j in g(i, left):
        e = dict(d)
        for k in j:
            e.setdefault(k, []).append(i)
        r = f(s, i+1, e)
        if r: return r
    return None

n = int(input())
n = 100
for i in range(100):
    s = n + i
    r = f(s, 1, {})
    if r:
        print(sum(len(x) for x in r.values()))
        for k,v in r.items():
            for x in v:
                print(k, x)
        break

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())

phi = 0 if N & 1 else 1
print(N * (N - 1) // 2 - N // 2)
for i in range(N):
    for j in range(i+1, N):
        k, l = i+1, j+1
        if l != N - k + phi:
            print(k, l)
### BUGGY CODE ###

import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
#from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=set()
br=set()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
             b.add((i,j))
             n[i*w+j]=0
        else:
            continue
while True:
    f=False
    update=False
    for z in b:
        i=z[0]
        j=z[1]
        if i<h-1 and a[i+1][j]=="." and n[(i+1)*w+j]==-1:
            br.add(((i+1),j))
            n[(i+1)*w+j]=0
            f=True
        if i>0 and a[i-1][j]=="." and n[(i-1)*w+j]==-1:
            br.add(((i-1),j))
            n[(i-1)*w+j]=0
            f=True
        if j<w-1 and a[i][j+1]=="." and n[i*w+(j+1)]==-1:
            f=True
            n[i*w+(j+1)]=0
            br.add((i,(j+1)))
        if j>0 and a[i][j-1]=="."  and n[i*w+(j-1)]==-1:
            f=True
            n[i*w+(j-1)]=0
            br.add((i,(j-1)))
    if f:
      c+=1
      update=True
    if not f:
      break
    b=set()
    b=b|br
    br=set()
print(c)
        

### FIXED CODE ###

import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
             b.append((i,j))
             n[i*w+j]=0
        else:
            continue
p = [(1,0),(-1,0),(0,1),(0,-1)]

while b:
    i,j=b.popleft()
    for s,t in p:
      if 0 <= i+s <= h-1 and 0 <= j+t <= w-1:
        if n[(i+s)*w+(j+t)]==-1:
          n[(i+s)*w+(j+t)]=n[i*w+j]+1
          c=max(c,n[i*w+j]+1)
          b.append(((i+s),(j+t)))
    
print(c)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
slis=[]
for i in range(len(s)-1):
	slis.append(s[i]+s[i+1])
for j in range(q):
	l,r=map(int,input().split())
	t_slis=slis[l-1:r-1]
	print(t_slis.count("AC"))


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    x = []
    for i in range(1, N):
        x.append(sum(A[i:]))

    ans = 0
    for i in range(N-1):
        ans += A[i] * x[i]
    ans = ans % (10**9 + 7)
    print(ans)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    x = [0] * N
    tot = 0
    for i in range(N-1, 0, -1):
        tot += A[i]
        x[i] = tot

    ans = 0
    for i in range(N-1):
        ans += A[i] * x[i+1]
    ans = ans % (10**9 + 7)
    print(ans)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

# from random import randint

MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
# N = 10000
# A = [randint(1, 10**6) for _ in range(N)]

def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    return gcd(b%a, a)
def lcm(a, b):
    return (a * b) // gcd(a, b)

a_lcm = A[0]
for a_i in A[1:]:
    a_lcm = lcm(a_lcm, a_i)

sum_num = 0
for a_i in A:
    sum_num = (sum_num + (a_lcm//a_i)) % MOD

print(sum_num)

### FIXED CODE ###

# from random import randint

MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
# N = 10000
# A = [randint(1, 10**6) for _ in range(N)]

def modinv(a):
    return pow(a, MOD-2, MOD)

# a = 12345678900000
# b = 100000
# a %= MOD
# print(a * modinv(b) % MOD)

def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    return gcd(b%a, a)
def lcm(a, b):
    return (a * b) // gcd(a, b)

a_lcm = A[0]
for a_i in A[1:]:
    a_lcm = lcm(a_lcm, a_i)
a_lcm %= MOD

sum_num = 0
for a_i in A:
    sum_num = (sum_num + (a_lcm * modinv(a_i))) % MOD

print(sum_num)
### BUGGY CODE ###

def main():
    H, W, D = map(int, input().split())
    A = [
        list(map(int, input().split()))
        for _ in range(H)
    ]
    Q = int(input())
    LR = [
        list(map(int, input().split()))
        for _ in range(Q)
    ]

    f(H, W, D, A, Q, LR)


def f(H, W, D, A, Q, LR):
    pos = [None for _ in range(H * W + 1)]
    for y in range(H):
        for x in range(W):
            a = A[y][x]
            pos[a] = (x, y)

    for l, r in LR:
        ans = 0
        current = l
        target = r
        while current != target:
            _next = current + D
            i, j = pos[current]
            x, y = pos[_next]

            dist = abs(x - i) + abs(y - j)
            ans += dist

            # print((j, i), "to", (y, x), "cur", current, "next", _next, dist)
            current = _next

        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, W, D = map(int, input().split())
    A = [
        list(map(int, input().split()))
        for _ in range(H)
    ]
    Q = int(input())
    LR = [
        list(map(int, input().split()))
        for _ in range(Q)
    ]

    f(H, W, D, A, Q, LR)


def f(H, W, D, A, Q, LR):
    """
    距離を計算しておく
    """
    pos = [None for _ in range(H * W + 1)]
    for y in range(H):
        for x in range(W):
            a = A[y][x]
            pos[a] = (x, y)

    d = [0 for _ in range(H * W + 1)]
    for i in range(1, D + 1):
        current = i
        dist = 0
        while current + D <= H * W:
            _next = current + D
            i, j = pos[current]
            x, y = pos[_next]

            dist += abs(x - i) + abs(y - j)

            # print((j, i), "to", (y, x), "cur", current, "next", _next, dist)
            d[_next] = dist
            current = _next

    # print(d)

    for l, r in LR:
        ans = d[r] - d[l]
        print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)

ansers = dict()
for i in range(N):
    if A[i] in ansers:
        print(ansers[A[i]])
    else:
        temp = sum(v*(v-1)//2 if A[i]!=k else (v-1)*(v-2)//2 for k, v in C.items())
        print(temp)
        ansers[A[i]] = temp

### FIXED CODE ###

from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)

MX = sum(v*(v-1) for v in C.values())//2
for i in range(N):
    print(MX-C[A[i]]+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
from copy import copy, deepcopy
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            ind = bisect_left(LIS,A[u])
            lis = copy(LIS)
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            dfs(u,lis)
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            if A[u] > LIS[-1]:
                LIS.append(A[u])
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,A[u])
                stack = LIS[ind]
                LIS[ind] = A[u]
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS[ind] = stack
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')