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

#!/usr/bin/env python3
import sys
import queue

def solve(H: int, W: int, black):
    Q = queue.Queue()
    marked = [[False] * W for h in range(H)]
    qlen = 0
    for h, w in black:
        Q.put((h, w))
        qlen += 1
        marked[h][w] = True
    
    count = 0
    while not Q.empty():
        flag = False
        for _ in range(qlen):
            h, w = Q.get()
            qlen -= 1
            for hh, ww in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
                if 0 <= hh <= H-1 and 0 <= ww <= W-1 and not marked[hh][ww]:
                    flag = True
                    Q.put((hh, ww))
                    qlen += 1
                    marked[hh][ww] = True
        if flag:
            count += 1
    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    black = []
    for h in range(H):
        line = next(tokens)
        for w, c in enumerate(line):
            if c == '#':
                black.append((h, w))
    solve(H, W, black)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    dist = [[inf] * W for h in range(H)]
    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == '#':
                dist[h][w] = 0
            else:
                dist[h][w] = min(dist[h-1][w], dist[h][w-1]) + 1
    
    dmax = 0
    for h in range(H-1, -1, -1):
        for w in range(W-1, -1, -1):
            if A[h][w] == '#':
                dist[h][w] = 0
            elif h+1 <= H-1 and w+1 <= W-1:
                dist[h][w] = min(dist[h][w], min(dist[h+1][w], dist[h][w+1]) + 1)
            elif w+1 == W and h+1 <= H-1:
                dist[h][w] = min(dist[h][w], dist[h+1][w] + 1)
            elif h+1 == H and w+1 <= W-1:
                dist[h][w] = min(dist[h][w], dist[h][w+1] + 1)
            dmax = max(dist[h][w], dmax)
    print(dmax) 
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

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

N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 2**31
dp = [INF for i in range(N+1)]
dp[0],dp[1] = 0,0
dp[2] = abs(h[1]-h[0])
for i in range(3,N+1):
    for k in range(1,min(i,K+1)):
        dp[i] = min(dp[i],dp[i-k]+abs(h[i-1]-h[i-1-k]))
print(dp[N])

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
h = [int(x) for x in input().split()]
h = np.array(h)
dp = np.zeros(N, dtype=int)
for i in range(1, N):
  j = max(0, i-K)
  dp[i] = min(dp[j:i]+np.abs(h[i]-h[j:i]))
print(dp[N-1])
### BUGGY CODE ###

N,M = map(int,input().split())
lists = []
cnt = 0
cnt_AC = 0
for i in range(M):
    L,R = map(int,input().split())
    L_R = list(range(L,R+1))
    lists.append(L_R)
for i in range(1,N+1):
    cnt = 0
    for j in range(M):
        if i in lists[j]:
            cnt += 1
    if cnt == M:
        cnt_AC += 1
print(cnt_AC)

### 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)
ans = list(range(max(L),min(R)+1))
print(len(ans))
### BUGGY CODE ###

a,b,n = map(int, input().split())
com = 0
if n < b:
    x = n
else:
    x = b-1
while x >= 0:
    val = (a*x)//b-a*(x//b)
    if val < com:
        pass
    else:
        com = val
    x -= 1
print(com)

### FIXED CODE ###

a,b,n = map(int, input().split())
com = 0
if n < b:
    x = n
else:
    x = b-1
val = (a*x)//b
print(val)
### BUGGY CODE ###

n,q = map(int, input().split())
a=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    a.append(tmp)

p=[]
for i in range(q):
    tmp = list(map(int,input().split()))
    p.append(tmp)

link = [[] for _ in range(n)]

for tmp in a:
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)

for tmp in p:
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = [False]*n
Q = deque()
Q.append([0,0])

while Q:
    node= Q.popleft()
    finish[node[0]]=True

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if not finish[nxt]:
            Q.append([nxt,val])

print(*ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = {0}
Q = deque()
Q.append([0,0])
while Q:
    node= Q.popleft()
    finish.add(node[0])

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if nxt in finish:
            pass
        else:
            Q.append([nxt,val])

print(*ans)
### BUGGY CODE ###

N,K=map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = (A[i]+1)/2
S=[]
for i in range(N-K+1):
    S += [sum(A[i:i+K])]
print(max(S))

### FIXED CODE ###

def main():
    N,K=map(int, input().split())
    A = list(map(int, input().split()))
    S = (sum(A[0:K])+K)/2
    S_max=S
    for i in range(K,N):
        S +=  A[i]/2
        S -= A[i-K]/2
        if S_max<S:
            S_max=S
    print(S_max)

main()
### BUGGY CODE ###

import sys

class UnionFind(object):
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0 for i in range(n + 1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

sys.setrecursionlimit(10 ** 5 + 1)

n, k, l = map(int, input().split())
Ur = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    Ur.union(p, q)

Ut = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    Ut.union(r, s)

x = [[Ur.find(i + 1), Ut.find(i + 1)] for i in range(n)]
ans = []
for i in range(n):
    ans.append(x.count(x[i]))
print(' '.join([str(a) for a in ans]))


### FIXED CODE ###

import sys
from collections import Counter

class UnionFind(object):
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0 for i in range(n + 1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

sys.setrecursionlimit(10 ** 5 + 1)

n, k, l = map(int, input().split())
Ur = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    Ur.union(p, q)

Ut = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    Ut.union(r, s)

x = [(Ur.find(i + 1), Ut.find(i + 1)) for i in range(n)]
c = Counter(x)
ans = []
for i in range(n):
    ans.append(c[x[i]])
print(' '.join([str(a) for a in ans]))
### BUGGY CODE ###

import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
tableud = [[0] * N for _ in range(N)]
tablelr = [[0] * N for _ in range(N)]
for i in range(N):
  x, y, _ = a[i]
  for j in range(N):
    tableud[i][j] = abs(a[j][0] - x) * a[j][2]
    tablelr[i][j] = abs(a[j][1] - y) * a[j][2]
for t in range(N + 1):
  res = float("inf")
  for c in combi([x for x in range(N)], t):
    for i in range(1 << t):
      table = [10 ** 20] * N
      for j in range(N):
        table[j] = min(abs(a[j][0]), abs(a[j][1])) * a[j][2]
      for j in range(t):
        if i & (1 << j):
          for k in range(N):
            table[k] = min(table[k], tableud[c[j]][k])
        else:
          for k in range(N):
            table[k] = min(table[k], tablelr[c[j]][k])
      res = min(res, sum(table))
  print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
table = [0] * N
for k in range(N): table[k] = min(abs(a[k][0]), abs(a[k][1])) * a[k][2]
tableudi = [10 ** 12 for _ in range((1 << N) * N)]
tablelri = [10 ** 12 for _ in range((1 << N) * N)]
for i in range(1 << N):
  for j in range(N):
    if i & (1 << j):
      for k in range(N):
        ud = min(abs(a[k][0] - a[j][0]) * a[k][2], table[k])
        lr = min(abs(a[k][1] - a[j][1]) * a[k][2], table[k])
        tableudi[i * N + k] = min(tableudi[i * N + k], ud)
        tablelri[i * N + k] = min(tablelri[i * N + k], lr)
    else:
      for k in range(N):
        tableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
        tablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
res = [10 ** 12] * (N + 1)
for t in range(1 << N):
  i = t + 0
  c = bin(t).count("1")
  while True:
    x = i + 0
    y = t ^ x
    rres = 0
    for j in range(N):
      rres += min(tableudi[x * N + j], tablelri[y * N + j])
    res[c] = min(res[c], rres)
    #print(t, res, rres)
    if i == 0: break
    i = (i - 1) & t
for r in res: print(r)
### BUGGY CODE ###

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

import numpy as np

A=np.array(A)
A.sort()
for op in BC:
    n=min(A[A<op[1]].size, op[0])
    if n > 0:
        A[:n]=op[1]
        A.sort()

print(A.sum())


### FIXED CODE ###

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

A.sort(reverse=True)
BC.sort(key=lambda x:x[1],reverse=True)

R=[]
n=0
for i in range(M):
    R.extend([BC[i][1]]*BC[i][0])
    n = n + BC[i][0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print(sum(R))
### BUGGY CODE ###



import numpy as np

n = int(input())
A = np.array([list(map(int,input().split())) for i in range(n)])

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = np.zeros(n, dtype="int")
#F = [[0 for i in range(n)] for j in range(2*n*n)]

n1n = n*(n-1)
nm2 = n - 2
nm1 = n - 1
maxga = n//2

d = 0
for ii in range(n*n*2):
    F = np.zeros(n, dtype="int")
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        si = S[i]
        if F[i] == 0 and si <= nm2:
            aite = A[i][si]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
        if co == nm1 or ga == maxga:
            break
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで
### BUGGY CODE ###

def checker(x,y):
	count_x_a = x.count('A')
	count_y_a = y.count('A')
	
	len_x = count_x_a*2 + (len(x)-count_x_a)
	len_y = count_y_a*2 + (len(y)-count_y_a)
	return (len_x-len_y)%3 == 0
	
s = input()
t = input()
q = int(input())

for _ in range(q):
	a, b, c, d = map(int, input().split())
	
	x = s[a-1:b]
	y = t[c-1:d]
	
	print(['NO', 'YES'][checker(x,y)]) 

### FIXED CODE ###

s = input()
t = input()
q = int(input())

len_s = len(s)
len_t = len(t)

s_counter= [0]*(len_s+1)
s_temp = 0
for i in range(len_s):
	if s[i] == "A":
		s_temp += 1
	s_counter[i+1] = s_temp
	
t_counter= [0]*(len_t+1)
t_temp = 0
for i in range(len_t):
	if t[i] == "A":
		t_temp += 1
	t_counter[i+1] = t_temp

for _ in range(q):
	a, b, c, d = map(int, input().split())
	
	x = s_counter[b]-s_counter[a-1]
	y = t_counter[d]-t_counter[c-1]
	print(['NO', 'YES'][((x+b-a+1)-(y+d-c+1))%3==0])
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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


class Node:
    def __init__(self, index):
        self.index = index
        self.point = 0

    def updatePoints(self, point):
        self.point += point


# 2*10**5
nodes = [Node(i) for i in range(1, n + 1)]

# 2*10**5
edges = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)


def memoize(f):
    memo = {}

    def memoized(*args):
        if args not in memo.keys():
            memo[args] = f(*args)
        return memo[args]
    return memoized

@memoize
def selectNode(p):
    selected = [p]
    ls = edges[p]
    selected += ls

    while True:
        if ls == []:
            break
        for x in ls:
            ls = edges[x]
            selected += ls
    return selected

for _ in range(q):
    p, x = map(int, input().split())
    node_index_list = selectNode(p)
    for idx, node in enumerate(nodes):
        if idx + 1 in node_index_list:
            node.updatePoints(x)

print(*(node.point for node in nodes))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())

graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)

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

def dfs(v1, parent, add):
    values[v1] += add
    for v2 in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, values[v1])

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

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        tb = []
        while True:
            if self.parents[x] < 0:
                for i in tb:
                    self.parents[i] = x
                return x
            else:
                tb.append(x)
                x = self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.reverse()
ans = []
nC2 = n * (n - 1) // 2

uf = UnionFind(n)
for a, b in ab:
    c = nC2
    for v in uf.parents:
        if v < -1:
            c -= v * (v + 1) // 2
    ans.append(c)
    uf.union(a-1, b-1)

ans.reverse()

for ai in ans:
    print(ai)


### FIXED CODE ###

def xC2(x):
    if x == 1:
        return 0
    else:
        return x * (x-1) // 2

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return 0

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        nx, ny = - self.parents[x],  - self.parents[y]

        self.parents[x] += self.parents[y]
        self.parents[y] = x

        return xC2(nx + ny) - xC2(nx) - xC2(ny)

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.reverse()
ans = [xC2(n)]

uf = UnionFind(n)
for a, b in ab:
    ans.append(ans[-1] - uf.union(a-1, b-1))

ans.reverse()

for ai in ans[1:]:
    print(ai)
### BUGGY CODE ###

import bisect

n = int(input())
a_li = list(map(int, input().split()))
b_li = list(map(int, input().split()))
c_li = list(map(int, input().split()))

a_li.sort()
b_li.sort()
c_li.sort()

ans = 0

for i in a_li:
    s = bisect.bisect_right(b_li, i)
    
    for j in b_li[s:]:
        t = bisect.bisect_right(c_li, j)
        ans += n-t
        
print(ans)

### FIXED CODE ###

import bisect

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

a.sort()
b.sort()
c.sort()

ans = 0

for middle in b:
    tmp1 = bisect.bisect_left(a, middle)
    tmp2 = bisect.bisect_right(c, middle)
    ans += tmp1 * (n - tmp2)

print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
a = 1
repeat_count = 0
while a*a <= n:
    b = 1
    while a*b < n:
        ans += 1
        if b * b > n:
            repeat_count += 1
        b += 1
    a += 1
print(ans + repeat_count)

### FIXED CODE ###

import math as mt
from collections import defaultdict
  
MAXN = 10**6
  
spf = [0 for i in range(MAXN)] 
  
def sieve(): 
    spf[1] = 1
    for i in range(2, MAXN): 
        spf[i] = i 
    for i in range(4, MAXN, 2): 
        spf[i] = 2
  
    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
        if (spf[i] == i): 
            for j in range(i * i, MAXN, i):  
                if (spf[j] == j): 
                    spf[j] = i 
  
# A O(log n) function returning prime  
# factorization by dividing by smallest  
# prime factor at every step 
def getFactorization(x): 
    d = defaultdict(int)
    while (x != 1): 
        #ret.append(spf[x])
        d[spf[x]] += 1 
        x = x // spf[x] 
    #return Counter(ret)
    ans = 1
    for i in d:
        ans *= (d[i]+1)
    return ans
sieve()

n = int(input())
ans = 0
for i in range(1, n):
    ans += getFactorization(i)
print(ans)
### BUGGY CODE ###

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

count = 0
for i in range(n):
    flg = True
    for j in range(i):
        if p[i] > p[j]:
            flg = False
    if flg:
        count += 1

print(count)

### FIXED CODE ###

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

m = p[0]
count = 1
for i in range(1,n):
    if m >= p[i]:
        count += 1
    m = min(m, p[i])
print(count)
### BUGGY CODE ###

#input = ["3 5","0 0 1","0 1 2","0 2 3","1 0 2","1 1 2"]
#input = ["1 3","1 0 0","0 0 5","1 0 0"]
#input = ["2 15","1 0 1","1 0 0","1 1 1","0 0 2","1 0 1","1 0 0","1 1 1","0 1 1","1 0 1","1 0 0","1 1 1","0 1 5","1 0 1","1 0 0","1 1 1"]
#input = ["1 5","1 0 0","0 0 5","1 0 0","0 0 8","1 0 0"]

l = raw_input().split()
#l=input[0].split()

n = int(l[0])
a = [2147483647]*50000
change = 1

for i in range(0,int(l[1])):
	l = raw_input().split()
#	l=input[i+1].split()
	if int(l[0])==0:
		a[int(l[1])]=int(l[2])
		change = 1
	elif change==1:
		m = min(a[int(l[1]):int(l[2])+1])
		print m
	else:
		print m

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
 
def main(init=int(2**31-1), readline=stdin.readline):
    n, q = (int(s) for s in readline().split())
 
    a = [init] * n
    b = [init] * ((n // 100) + 1)
 
    for _ in range(q):
        com, x, y = (int(s) for s in readline().split())
        if com:
            bx = x - (x % 100) + 100
            by = y - (y % 100)
            if bx < by:
                m = min(min(a[x:bx]), min(b[bx//100:by//100]),
                        min(a[by:y+1]))
            else:
                m = min(a[x:y+1])
            print(m)
        else:
            a[x] = y
            bx = x - (x % 100)
            b[x//100] = min(a[bx:bx+100])
 
 
main()
### BUGGY CODE ###

import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = [0 for i in range(10 ** 6)]
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    if memo[tmp] == 0:
      memo[tmp] = C(tmp, 2)
      ans += memo[tmp]
    else:
      ans += memo[tmp]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else:
    if memo[tmp - 1] == 0:
      print(ans - (memo[tmp] - C(tmp-1, 2)))
    else:
      print(ans - (memo[tmp] - memo[tmp-1]))


### FIXED CODE ###

import math

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = [0 for i in range(10 ** 6)]
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    if memo[tmp] == 0:
      memo[tmp] = tmp * (tmp - 1) // 2
      ans += memo[tmp]
    else:
      ans += memo[tmp]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else:
    print(ans - tmp * (tmp - 1) // 2 + (tmp - 1) * (tmp - 2) // 2)