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

import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if union[i] is union[j]:continue
    tmp = union[j][:]
    while tmp:
        k = heapq.heappop(tmp)
        heapq.heappush(union[i],k)
        union[k] = union[i]
    ans += c
    cnt += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)
### BUGGY CODE ###

def main():
    n, w = map(int, input().split())
    dp = {}
    dp[0] = 0
    item = [list(map(int, input().split())) for _ in range(n)]
    item.sort()
    for i in range(n):
        buf = []
        for v in dp.keys():
            if v + item[i][0] > w:
                continue
            if v + item[i][0] in dp.keys() and dp[v] + item[i][1] > dp[v+item[i][0]]:
                buf.append([v+item[i][0], dp[v] + item[i][1]])
            else:
                buf.append([v+item[i][0], dp[v] + item[i][1]])
        for j in range(len(buf)):
            dp[buf[j][0]] = buf[j][1]
    print(max(dp.values()))

if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

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

def resolve():
    n = int(input())
    p = list(map(int, input().split()))
    ans = 0
    while any(i + 1 == p[i] for i in range(n)):
        for i in range(n - 1):
            if i + 1 == p[i]:
                p[i], p[i + 1] = p[i + 1], p[i]
                ans += 1
    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    n = int(input())
    p = list(map(int, input().split()))
    ans = 0
    if p[0] == 1:
        p[0], p[1] = p[1], p[0]
        ans += 1
    if p[n - 1] == n:
        p[n - 2], p[n - 1] = p[n - 1], p[n - 2]
        ans += 1
    for i in range(n - 1):
        if p[i] == i + 1:
            p[i], p[i + 1] = p[i + 1], p[i]
            ans += 1
    print(ans)


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

n = int(input())
data = []

for i in range(n):
	command = input().split()
	if len(command) == 2:
		command,x = command
	else:
		command = command[0]
	if command == 'insert':
		data.insert(0,x)
	elif command == 'delete':
		if x in data:
			data.remove(x)
	elif command == 'deleteFirst':
		data.pop(0)
	elif command == 'deleteLast':
		data.pop()

print(*data)

### FIXED CODE ###

from collections import deque

n = int(input())
data = deque()

for i in range(n):
	command = input().split()
	if len(command) == 2:
		command,x = command
	else:
		command = command[0]
	if command == 'insert':
		data.appendleft(x)
	elif command == 'delete':
		if x in data:
			data.remove(x)
	elif command == 'deleteFirst':
		data.popleft()
	elif command == 'deleteLast':
		data.pop()

print(*data)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
for i in range(q):
	a,b,c=map(str, input().split())
	if a=="1":
		f=list(s)
		f[int(b)-1]=c
		s="".join(f)
	if a=="2":
		print(len(set(s[int(b)-1:int(c)])))

### FIXED CODE ###

n = int(input())
stmp = list(input())
Q = int(input())
target = ord("a")
s = [ord(stmp[i])-target for i in range(n)]

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)
	
	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def __init__(self, n):
		self.bitlen = n+1
		self.bit = [0]*(n+1)

b = [BIT(n) for i in range(26)]
for i in range(n):
	b[s[i]].add(i, 1)

for _ in range(Q):
	q,qtmpa,qtmpb = input().split()
	if q[0] == "1":
		qa = int(qtmpa)
		t = ord(qtmpb)-target
		b[t].add(qa-1, 1)
		b[s[qa-1]].add(qa-1, -1)
		s[qa-1] = t
	else:
		ans = 0
		qta = int(qtmpa)
		qtb = int(qtmpb)
		for i in range(26):
			if b[i].sum(qta-1, qtb) != 0:
				ans += 1
		print(ans)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
P = list(map(int, input().split()))

ans4 = list()
ans2 = list()
for i in range(n - (k-1)):
    ans2.append(P[i:i+k])
    ans4.append(sum(P[i:i+k]))

am = np.argmax(ans4)
am2 = P[am:am+k]
ans = 0
for i in am2:
    for j in range(1, i + 1):
        ans += j / i
print(ans)

### FIXED CODE ###

from itertools import accumulate

n,k = map(int,input().split())
P = list(map(int,input().split()))

# 期待値の前計算
expP = [(P[i]+1)/2 for i in range(n)]

# 累積和の計算
acc = [0]+ list(accumulate(expP)) # 0を忘れずに

# 隣接する K 項の和の計算
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = ["".join(sorted(list(input()))) for _ in range(n)]
ans = 0
for v in combinations(s, 2):
    if v[0] == v[1]:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())


cnt = 0
tmpdic = {}
for i in s:
    tmp = "".join(sorted(i))
    if tmp in tmpdic.keys():
        cnt += tmpdic[tmp]
        tmpdic[tmp] += 1
    else:
        tmpdic[tmp] = 1


print(cnt)
### BUGGY CODE ###


n, k = input().split()
N = int(n)
K = int(k)
p = input().split()
P = list(map(int, p))

tmp = 0
ans = []
for i in range(K, N + 1, 1):
    for j in range(i - K, i, 1):
        tmp += (P[j] * (P[j] + 1) / 2 / P[j])
    ans.append(tmp)
    tmp -= tmp

print(max(ans))

### FIXED CODE ###

n, k = input().split()
N = int(n)
K = int(k)
p = input().split()
P = list(map(int, p))
 
tmp = 0
num = 0
hoge = 0
ans = []
for i in range(N):
    tmp += (P[i] * (P[i] + 1) / 2 / P[i])
    ans.append(tmp)
    tmp -= tmp
    if i == (K-1):
        num = sum(ans[0:K])
        hoge = num
    elif i > (K-1):
        num = num - ans[i-K] + ans[i]
        if num > hoge:
            hoge = num
print(hoge)
### BUGGY CODE ###

N , K = (int(i) for i in input().split())
a = 0
b = 0
c = 0
count = 0
for i in range(N):
    a = i+1
    for j in range(N):
        b = j + 1
        for k in range(N):
            c = k + 1
            if (a+b)%K==0 and (b+c)%K==0 and (c+a)%K==0:
                count += 1
print(count)

### FIXED CODE ###

N, K = map(int, input().split())
res = 0
res += (N // K)** 3
if K % 2 == 0:
    res += ((N-K//2)//K + 1) ** 3

print(res)
### BUGGY CODE ###

n = int(input())

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

q = int(input())

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


def func1(lst, value):
    return [i for i, x in enumerate(lst) if x == value]

for i in range(q):
    if a.count(bc[i][0]) == 0 :
        print(sum(a))
    else :
        idx = func1(a,bc[i][0])
        for j in idx :
            a[j]=bc[i][1]
        print(sum(a))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = [list(map(int,input().split())) for i in range(q)]
list = [0]*(10**5)
for i in range(n) :
    list[a[i]-1] += 1

wa = sum(a)

for i in range(q) :
    wa += (bc[i][1]-bc[i][0])*list[bc[i][0]-1]
    print(wa)
    list[bc[i][1]-1] += list[bc[i][0]-1]
    list[bc[i][0]-1] = 0
### BUGGY CODE ###

import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
tree = [a[0]]

for i in range(1,n):
  index = bisect.bisect_left(tree, a[i])
  if index == 0:
    bisect.insort(tree, a[i])
  else:
    tree[index-1] = a[i]
print(len(tree))

    


    
    

### FIXED CODE ###

import bisect
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]
tree = deque([]) 
tree.append(a[0])

for a in a[1:]:
  index = bisect.bisect_left(tree, a)
  if index == 0:
    tree.appendleft(a)
  else:
    tree[index-1] = a
print(len(tree))
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))

dp=[100000]*n
dp[0]=0
for i in range (1,n):
    if i<k:
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),abs(h[i]-h[0]))
    else:
        dp[i]=dp[i-k]+abs(h[i]-h[i-k])
        for j in range(1,k):
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))

dp=[1000000000]*n
dp[0]=0
for i in range (1,n):
    for j in range(max(i-k,0),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
S = input()
List=list(S)
flag=True
mid = ""
res = 0
for i in range(N):
  if List[i] == "R":
    pass
  else:
    for j in range(N-1,-1,-1):
      if i == j:
        flag=False
        break
      if List[j] == "R":
        List[i]="R"
        List[j]="W"
        res += 1
        break
  if flag == False:
    break
for i in range(N-1):
  if List[i] == "W" and List[i+1] == "R":
    List[i+1] == "W"
    res +=1
    break
print(res)

### FIXED CODE ###

N = int(input())
S = input()
List=list(S)
flag=True
mid = ""
res = 0
n = List.count("R")
k=0
for i in range(n):
  if List[i] == "W":
    res += 1
print(res)
### BUGGY CODE ###

import sys
from collections import defaultdict
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, X, Y = [int(x) for x in input().strip().split()]
G = np.zeros((N, N), dtype=int)
D = defaultdict(int)
for k in range(1, N):
    for k2 in range(k+1, N+1):
        D[min(k2 - k, abs(X-k) + 1 + abs(Y-k2), abs(Y-k) + 1 + abs(X-k2))] += 1

for k in range(1, N):
    print(D[k])


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, X, Y = [int(x) for x in input().strip().split()]
D = defaultdict(int)
for k in range(1, N):
    for k2 in range(k+1, N+1):
        D[min(k2 - k, abs(X-k) + 1 + abs(Y-k2), abs(Y-k) + 1 + abs(X-k2))] += 1

for k in range(1, N):
    print(D[k])
### BUGGY CODE ###

k=int(input())
ans=0
dev=7
while dev%k and ans <=k+3:
    ans+=1
    dev+=(7*(10**ans))%k
if ans==k+4:print(-1)
else:print(ans+1)

### FIXED CODE ###

k=int(input())
ans=0
dev=7
while dev%k and ans <=k+3:
    ans+=1
    dev+=7*pow(10,ans,k)
    dev%=k
if ans==k+4:print(-1)
else:print(ans+1)
### BUGGY CODE ###

k=int(input())
import math
ans=0
for i in range(1,k+1):
	
        for j in range(1,k+1):
		
                for l in range(1,k+1):
			
                        ans+=math.gcd(i,math.gcd(j,l))
print(ans)


### FIXED CODE ###

import math

K = int(input())

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        x = math.gcd(i, j)
        for k in range(1, K+1):
            ans += math.gcd(x, k)

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

s = str(input())
q = int(input())
for i in range(q):
    tmp=tuple(map(str, input().split()))
    if len(tmp)==3: #pattern 2
        if int(tmp[1])==1:
            s=tmp[2]+s
        else:
            s+=tmp[2]
    else:
        s=s[::-1]

print(s)

### FIXED CODE ###

from collections import deque
s = str(input())
q = int(input())
stat = 0
l = []
a = deque()
b = deque()
for i in range(q):
    l = list(map(str, input().split()))
    t = int(l[0])
    if t == 1:
        stat += 1
    else:
        f = int(l[1])
        c = l[2]
        if stat % 2 == 0:
            if f == 1:
                a.appendleft(c)
            else:
                b.append(c)
        else:
            if f == 1:
                b.append(c)
            else:
                a.appendleft(c)

#print(a, b, stat % 2)
ans = ''.join(a)+s+''.join(b)
if stat % 2 == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

import numpy as np

R, C, K = map(int,input().split())
MAP = np.zeros((R, C), dtype=np.int64)
DP = np.zeros((R+1, C+1, 4), dtype=np.int64)

for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v

for i in range(R):
    for j in range(C):
        DP[i+1][j+1][0] = max(DP[i+1][j+1][0], DP[i][j+1].max())
        DP[i+1][j+1][1] = max(DP[i+1][j+1][1], DP[i][j+1].max() + MAP[i][j])
        DP[i+1][j+1] = np.amax([DP[i+1][j+1], DP[i+1][j]], axis=0)
        DP[i+1][j+1][1:] = np.amax([DP[i+1][j+1][1:], DP[i+1][j][:3] + MAP[i][j]], axis=0)

print(max(DP[R][C]))

### FIXED CODE ###

R, C, K = map(int,input().split())
MAP = [[0 for i in range(C)] for j in range(R)]
DP = [[[0 for i in range(C+1)] for j in range(4)] for k in range(R+1)]
 
for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v
 
for i in range(R):
    for j in range(4):
        for k in range(C):
            DP[i+1][j][k+1] = max(DP[i][3][k+1], DP[i+1][j][k])
            if j == 0:
                continue
            v = MAP[i][k]
            if v == 0:
                continue
            DP[i+1][j][k+1] = max(DP[i+1][j][k+1], max(DP[i][3][k+1], DP[i+1][j-1][k]) + v)

print(DP[R][3][C])
### BUGGY CODE ###

import decimal
n = int(input())
a=[input() for i in range(n)]
biga=[]
for i in range(n):
    num = decimal.Decimal(a[i])
    biga.append(int(num*10**9))

def fact25(n):
    cnt2=0
    cnt5=0
    while True:
        if n%2==0:
            n//=2
            cnt2+=1
        else:
            break
    while True:
        if n%5==0:
            n//=5
            cnt5+=1
        else:
            break
    return cnt2,cnt5

arr = [[0 for _ in range(50)] for _ in range(50)]
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    arr[cnt2][cnt5]+=1
ans=0
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    n2=18-cnt2
    n5=18-cnt5
    arr[cnt2][cnt5]-=1
    for j in range(50): # 2
        for k in range(50): # 5
            if j>=n2 and k>=n5:
                ans+=arr[j][k]
    arr[cnt2][cnt5]+=1

print(ans//2)

### FIXED CODE ###

import decimal
n = int(input())
a=[input() for i in range(n)]
biga=[]
for i in range(n):
    num = decimal.Decimal(a[i])
    biga.append(int(num*10**9))
def fact25(n):
    cnt2=0
    cnt5=0
    while n%2==0:
        n//=2
        cnt2+=1
    while n%5==0:
        n//=5
        cnt5+=1
    return cnt2,cnt5

arr = [[0 for _ in range(20)] for _ in range(20)]
p25 = []
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    p25.append([cnt2,cnt5])
    cnt2=min(19,cnt2)
    cnt5=min(19,cnt5)
    arr[cnt2][cnt5]+=1

ans=0
for i in range(20): # 2
    for j in range(20): # 5
        if arr[i][j]==0:
            continue
        for k in range(20): # 2
            for l in range(20): # 5
                if i+k>=18 and j+l>=18:
                    if i==k and j==l:
                        ans+= (arr[i][j]-1)*arr[k][l]
                    else:
                        ans+= arr[i][j]*arr[k][l]

print(ans//2)
### BUGGY CODE ###

s = input()
data = []
for i in range(len(s)):
    if s[i] == 'A':
        
        for j in range(i+1,len(s)):
           
            if s[j] == 'Z':
                data.append(j-i+1)
print(max(data))            

### FIXED CODE ###

s = input()
a = []
z = []
for i in range(len(s)):
    if s[i] == 'A':
        a.append(i)
    if s[i] == 'Z': 
        z.append(i)
print(z[-1]-a[0]+1)
### BUGGY CODE ###

S=input()
while "ST" in S:
    S=S.replace("ST","")
print(len(S))

### FIXED CODE ###

from collections import deque
S=list(map(lambda x: 1 if x=="T" else 0,input()))

q=deque()

for i in S:

    if i:
        if (not q) or q[-1]!=0:
            q.append(i)
        elif q and q[-1]==0:
            q.pop()
    else:
        q.append(i)
print(len(q))
### BUGGY CODE ###

import numpy as np
from itertools import groupby

h,w=map(int,input().split())
M=np.array([list(input()) for i in range(h)])
C=np.array([[0]*w for i in range(h)])
R=np.array([[0]*w for i in range(h)])
L=np.array([[0]*w for i in range(h)])

for i in range(w):
	c=0
	for k,g in groupby(M[:,i]):
		l=len(list(g))
		if k=='#':
			C[c:c+l,i]=0
		else:
			C[c:c+l,i]=l
		c+=l

for i in range(h):
	c=0
	for k,g in groupby(M[i,:]):
		l=len(list(g))
		if k=='#':
			R[i,c:c+l]=0
		else:
			R[i,c:c+l]=l
		c+=l

r=0
for i in range(h):
	for j in range(w):
		r=max(r,C[i][j]+R[i][j]-1)
print(r)


### FIXED CODE ###

h,w=map(int,input().split())
M=[list(input()) for i in range(h)]
D=[[0]*w for i in range(h)]
U=[[0]*w for i in range(h)]
R=[[0]*w for i in range(h)]
L=[[0]*w for i in range(h)]

for i in range(h):
    c=0
    for j in range(w):
        if M[i][j]=='.':
            c+=1
            R[i][j]=c
        else:
            c=0
for i in range(h):
    c=0
    for j in range(w):
        if M[i][w-1-j]=='.':
            c+=1
            L[i][w-1-j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[i][j]=='.':
            c+=1
            D[i][j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[h-1-i][j]=='.':
            c+=1
            U[h-1-i][j]=c
        else:
            c=0
r=0
for i in range(h):
    for j in range(w):
        r=max(r,R[i][j]+L[i][j]+D[i][j]+U[i][j]-3)
print(r)
### BUGGY CODE ###

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,max):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

mod = 10**9+7

K = int(input())
S = input()
N = len(S)
max = N+K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    x = COM(N+K-i-1,N-1)
    y = pow(26,i,mod)
    z = pow(25,K-i,mod)
    xyz = (x*y*z)%mod
    ans = (ans+xyz)%mod
print(ans)


### FIXED CODE ###

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,max):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

mod = 10**9+7

K = int(input())
S = input()
N = len(S)
max = N+K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
modlist1 = []
modlist2 = []
a = 1
b = 1
for i in range(K+1):
    modlist1.append(a)
    modlist2.append(b)
    a = a*26%mod
    b = b*25%mod

ans = 0
for i in range(K+1):
    x = COM(N+K-i-1,N-1)
    y = modlist1[i]
    z = modlist2[K-i]
    xyz = ((x*y%mod)*z)%mod
    ans = (ans+xyz)%mod
print(ans)
### BUGGY CODE ###

N = int(input())

c = [[0 for i in range(9)] for i in range(9)]

for i in range(9):
  for j in range(9):
    for n in range(1, N+1):
      if (n % 10) == j+1 and int(str(n)[0]) == i+1:
        c[i][j] += 1
        
ans = 0
for i in range(9):
  for j in range(9):
    ans = ans + c[i][j]*c[j][i]
print(ans)

### FIXED CODE ###

N = int(input())

c = [[0 for i in range(10)] for i in range(10)]

for n in range(1, N+1):
  i = int(str(n)[0])
  j = n % 10
  c[i][j] += 1

ans = 0
for i in range(10):
  for j in range(10):
    ans = ans + c[i][j]*c[j][i]
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
    s = input()
    subsrings = []
    K = int(input())
    for i in range(len(s)):
        subsrings.append(s[i:])
    subsrings.sort()

    first = set()

    for s in subsrings:
        for i in range(1, len(s) + 1):
            if s[:i] not in first:
                first.add(s[:i])
                if len(first) == K:
                    print(s[:i])
                    break


### FIXED CODE ###

if __name__ == "__main__":
    s = input()

    K = int(input())

    subsrings = [s[i : i + K + 1] for i in range(len(s))]
    subsrings.sort()

    first = set()

    for s in subsrings:

        for i in range(1, len(s) + 1):
            if s[:i] not in first:
                first.add(s[:i])
                if len(first) == K:
                    print(s[:i])
                    break
### BUGGY CODE ###

from sys import stdin
from collections import deque


def get_adj_list(num_nodes, data, undirected=True):
    # adj_list ex) {1:[2,3,4], 2:[1,4,5], 3:[1,4], 4:[1,2,3,5], 5:[2,4]}
    graph = {}
    for i in range(num_nodes):
        graph[i+1] = []
    for val in data:
        x, y = val
        graph[x] = graph[x] + [y]
        if undirected:
            graph[y] = graph[y] + [x]
    return graph


def breadth_first_search(adj_list, start_node):
    dist = {}
    queue = deque([(start_node, 0)])
    while len(queue) > 0:
        v, d = queue.popleft()
        if v in dist: continue
        dist[v] = d
        for u in adj_list[v]:
            if u not in dist:
                queue.append((u, d+1))
    return dist

# bfs
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_list = []
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        dist_list.append(breadth_first_search(adj_list, i+1))
    for i in range(N):
        for j in range(i, N):
            dist_cnt[dist_list[i][j+1]] += 1
    for i in range(1, N):
        print(dist_cnt[i])

# 解説のコード
# def get_result(data):
#     N, X, Y = data
#     dist_cnt = [0 for i in range(N)]
#     for i in range(1, N+1):
#         for j in range(i+1, N+1):
#             min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
#             dist_cnt[min_dist] += 1
#     for i in range(1, N):
#         print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

### FIXED CODE ###

from sys import stdin


def get_result(data):
    N, X, Y = data
    dist_cnt = [0 for i in range(N)]
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
            dist_cnt[min_dist] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)
### BUGGY CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

ans_dict = {}
ans_keys = []
value_dict = {1: 0}
value_keys = [1]
for i in range(n):
    num = a_list[i]
    if num in ans_keys:
        print(ans_dict[num])
    else:
        buff = a_list[:i]
        buff.extend(a_list[i+1:])
        c = Counter(buff)

        tmp_ans = 0
        for value in c.values():
            if value in value_keys:
                tmp_ans += value_dict[value]
            else:
                tmp = int((value * (value - 1))/2)
                tmp_ans += tmp
                value_dict[value] = tmp
                value_keys.append(value)
        ans_dict[num] = tmp_ans
        ans_keys.append(num)
        print(tmp_ans)



### FIXED CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

c = Counter(a_list)

all_count = 0
for value in c.values():
    if value == 1:
        continue
    else:
        tmp = int((value * (value - 1))/2)
        all_count += tmp

for i in a_list:
    print(all_count - c[i] + 1)