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

import sys
#sys.setrecursionlimit(n)
import heapq
from collections import defaultdict, deque
import itertools

import itertools
from heapq import heappop, heappush
N, M, R = map(int, input().split())

r = [int(i) for i in input().split()]
mp = defaultdict(lambda:defaultdict(list))
for _ in range(M):
    a, b, c= map(int, input().split())
    mp[a][b] = c
    mp[b][a] = c

v = [[float('inf')] * (N + 1) for _ in [0] * (N + 1)]
def dijkstra(start):
    q = []
    global v
    heapq.heappush(q, (0, start))
    vv = v[start]
    vv[start] = 0
    while(q):
        vc, vs = heapq.heappop(q)
        for i in mp[vs]:
            vsc = mp[vs][i]
            cost = vv[i]
            newcost = vsc + vc
            if cost > newcost:
                vv[i] = newcost
                heapq.heappush(q, (newcost, i))

ans = float('inf')
for i in range(N + 1):
    dijkstra(i)

ans = float('inf')
for i in itertools.permutations(r):
    t_ans = 0
    for j in range(R - 1):
        t_ans += v[i[j]][i[j + 1]]
    if ans > t_ans:
        ans = t_ans
print(ans)


### FIXED CODE ###

import sys
#sys.setrecursionlimit(n)
import heapq
from collections import defaultdict, deque
import itertools

import itertools
from heapq import heappop, heappush
N, M, R = map(int, input().split())

r = [int(i) for i in input().split()]
mp = defaultdict(lambda:defaultdict(list))
for _ in range(M):
    a, b, c= map(int, input().split())
    mp[a][b] = c
    mp[b][a] = c

v = [[float('inf')] * (N + 1) for _ in [0] * (N + 1)]
def dijkstra(start):
    q = []
    global v
    heapq.heappush(q, (0, start))
    vv = v[start]
    vv[start] = 0
    while(q):
        vc, vs = heapq.heappop(q)
        for i in mp[vs]:
            vsc = mp[vs][i]
            cost = vv[i]
            newcost = vsc + vc
            if cost > newcost:
                vv[i] = newcost
                heapq.heappush(q, (newcost, i))

for i in r:
    dijkstra(i)

ans = float('inf')
for i in itertools.permutations(r):
    t_ans = 0
    for j in range(R - 1):
        t_ans += v[i[j]][i[j + 1]]
    if ans > t_ans:
        ans = t_ans
print(ans)
### BUGGY CODE ###

from collections import deque, defaultdict


graph = defaultdict(set)
banned = defaultdict(set)

N, M, K = map(int, input().split())
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)


res = [0] * (N + 1)
for i in range(1, N + 1):
    queue = deque([i])
    seen = {i}
    while queue:
        cur = queue.popleft()
        if i != cur and cur not in graph[i] and cur not in banned[i]:
            res[i] += 1
        for nxt in graph[cur]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
print(*res[1:])

### FIXED CODE ###

N, M, K = map(int, input().split())
graph = {i: set() for i in range(1, N + 1)}
banned = {i: set() for i in range(1, N + 1)}

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)

# BFS
group = {i: -1 for i in range(1, N + 1)}
count = {i: 0 for i in range(1, N + 1)}
for i in range(1, N + 1):
    if group[i] >= 0:
        continue
    queue = [i]
    group[i] = i
    count[i] += 1
    while queue:
        new = []
        for cur in queue:
            for nxt in graph[cur]:
                if group[nxt] == -1:
                    group[nxt] = group[cur]
                    count[group[nxt]] += 1
                    new.append(nxt)
        queue = new

res = [0] * N
# Remove itself
for i in range(N):
    res[i] = count[group[i + 1]] - 1

# Remove friends and blocked users
for i in range(N):
    for j in banned[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
    for j in graph[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
print(*res)
### BUGGY CODE ###

from operator import itemgetter
import sys

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の３つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

e = []
for i in range(n):
    e.append([i,a[i]/b[i],a[i],b[i]])

e.sort(key=itemgetter(1),reverse=True)
mea = e[0][1]
asum = 0
bsum = 0
min_bsum = 9999999999999999999

path = [0]*(10**4+1)
#path = [0]*(40)

depth = 0
while 1:
    #攻撃番号を得る
    anum = path[depth]

    #有効な攻撃か確認
    if anum > n-1:
        #攻撃ネタ切れなので１つ戻る
        path[depth] = 0
        depth -= 1
        if depth < 0: #深さ０に候補無しなので終了
            break
        anum = path[depth]
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue

    #攻撃実施
    asum = asum + e[anum][2]
    bsum = bsum + e[anum][3]
#    print("途中",h,asum,bsum,min_bsum,path[:depth])

    #攻撃後の状況チェック
    if asum >= h:
        if bsum < min_bsum:
            min_bsum = bsum
#            print("min更新",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
#    elif bsum >= min_bsum:    #積めないので 次の攻撃に行く
    elif (h-asum)/mea + bsum >= min_bsum:    #最大効率で積んだとしてオーバーなので次の攻撃に行く
#        print("オーバー",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue
    else:
        depth += 1

print(min_bsum)

### FIXED CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])
### BUGGY CODE ###

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

ans = []
for i in range(1, n+1):
    rank = lst.index(i) + 1
    ans.append(str(rank))


print(' '.join(ans))


### FIXED CODE ###

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


tmp = [0] * (n+1)
for i, num in enumerate(lst):
    tmp[num] = str(i + 1)

tmp.pop(0)

print(' '.join(tmp))
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
e=0
f=a%c
g=a%d
for j in range(b-a+1):
  if (f+j)%c!=0 and (g+j)%d!=0:
    e+=1
print(e)
  

### FIXED CODE ###

import fractions 
a,b,c,d=map(int,input().split())
f=lambda n:n-(n//c+n//d-n//(c*d//fractions.gcd(c,d)))
print(f(b)-f(a-1))
### BUGGY CODE ###

def LI():return list(map(int,input().split()))
INF=float("inf")
from collections import deque
def main():
    h,w,k=LI()
    x1,y1,x2,y2=LI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    maze=list(list(input()) for _ in range(h))
    dist=[[INF]*(w) for _ in range(h)]
    q=deque([])
    q.append((x1,y1))
    dist[x1][y1]=0
    while q:
        x,y=q.popleft()
        for vx,vy in ([0,1],[0,-1],[1,0],[-1,0]):
            flg=True
            for kk in range(1,k+1):
                if not flg:
                    break
                nx=x+kk*vx
                ny=y+kk*vy
                if not(0<=nx<h) or not(0<=ny<w):
                    break
                if maze[nx][ny]=="@":
                    flg=False
                    break
                if dist[nx][ny]<=dist[x][y]:
                    break
                dist[nx][ny]=dist[x][y]+1
                q.append((nx,ny))
    ans=dist[x2][y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()


### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                continue
            if maze[nx][ny]=="@":
                break
            if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
                break
            if cost[nx][ny]!=-1:
                continue
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))


# pp(cost)
ans=cost[x2][y2]
print(ans)
### BUGGY CODE ###

n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = []
for i, (x, d) in enumerate(xd, 1):
    xx.append([i, x, 0])
    xx.append([i, x + d - 0.5, 1])

xx.sort(key=lambda x: x[1])

adj = [[] for _ in range(n + 1)]
now = {0}
stack = [(INF, 0)]
for i, x, remove in xx:
    if remove:
        now.remove(i)

    else:
        while stack[-1][1] not in now:
            stack.pop()

        px, pi = stack[-1]
        adj[pi].append(i)

        now.add(i)
        stack.append([x, i])

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

dp = [1] * (n + 1)
for u in order[::-1]:
    for v in c[u]:
        dp[u] *= dp[v]
        dp[u] %= mod

    dp[u] += 1
    dp[u] %= mod

ans = dp[0] - 1
ans %= mod
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    xd = [map(int, input().split()) for _ in range(n)]
    mod = 998244353
    INF = 10 ** 10

    xx = [(x, x + d, i) for i, (x, d) in enumerate(xd, 1)]
    xx.sort()
    adj = [[] for _ in range(n + 1)]
    stack = [(INF, 0)]
    for l, r, i in xx:
        while stack[-1][0] <= l:
            stack.pop()

        ip = stack[-1][1]
        adj[ip].append(i)
        stack.append((r, i))

    stack2 = [0]
    d = [-1] * (n + 1)
    d[0] = 0
    c = [[] for _ in range(n + 1)]
    order = []
    while stack2:
        u = stack2.pop()
        order.append(u)
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                c[u].append(v)
                stack2.append(v)

    dp = [1] * (n + 1)
    for u in order[::-1]:
        for v in c[u]:
            dp[u] *= dp[v]
            dp[u] %= mod

        dp[u] += 1
        dp[u] %= mod

    ans = dp[0] - 1
    ans %= mod
    print(ans)


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

K = int(input())
n = 7
c = 0
while 1:
  m = n % K
  c += 1
  if m == 0:
    break
  tmp = m * 10 + 7
  if tmp == n:
    print(-1)
    exit()
  n = tmp
print(c)

### FIXED CODE ###

K = int(input())
n = 7
c = 0
while c <= K:
  n %= K
  c += 1
  if n == 0:
    print(c)
    exit()
  n = n * 10 + 7
print(-1)
### BUGGY CODE ###

h,n = map(int,input().split())
mahou = []
for i in range(n):
	a,b = map(int,input().split())
	mahou.append((a,b))
dp = [10**18 for _ in range(h+1)]
dp[0] = 0
for i in range(h+1):
	for j, k in mahou:
		if j+i <= h:
			dp[j+i] = min(dp[i]+k, dp[j+i])
		else:
			dp[h] = min(dp[i]+k, dp[h])
print(dp[h])

### FIXED CODE ###

h,n = map(int,input().split())
mahou = []
for i in range(n):
	a,b = map(int,input().split())
	mahou.append((a,b))
dp = [10**18 for _ in range(h+1)]
dp[0] = 0
for i in range(h+1):
	for j, k in mahou:
		if j+i <= h:
			dp[j+i] = min(dp[i]+k, dp[j+i])
		else:
			dp[h] = min(dp[i]+k, dp[h])
print(dp[h])
### BUGGY CODE ###

import math
N = int(input())
S = str(input())
r=0
g=0
b=0
error=0
n=0

if N%2==0:
    n=(N//2)-1
else:
    n=N//2

for i in range(N):
    if S[i]=='R':
        r+=1
    if S[i]=='G':
        g+=1
    if S[i]=='B':
        b+=1

for p in range(n+1):
    for i in range(N-(p*2)):
        if S[i]=='R' and S[i+p]=='G' and S[i+2*p]=='B':
            error+=1
        if S[i]=='R' and S[i+p]=='B' and S[i+2*p]=='G':
            error+=1
        if S[i]=='B' and S[i+p]=='R' and S[i+2*p]=='G':
            error+=1
        if S[i]=='B' and S[i+p]=='G' and S[i+2*p]=='R':
            error+=1
        if S[i]=='G' and S[i+p]=='R' and S[i+2*p]=='B':
            error+=1
        if S[i]=='G' and S[i+p]=='B' and S[i+2*p]=='R':
            error+=1
d=r*g*b

print(d-error)

### FIXED CODE ###

import math
N = int(input())
S = str(input())
r=0
g=0
b=0
error=0
n=0

if N%2==0:
    n=(N//2)-1
else:
    n=N//2

for i in range(N):
    if S[i]=='R':
        r+=1
    if S[i]=='G':
        g+=1
    if S[i]=='B':
        b+=1

for p in range(n+1):
    for i in range(N-(p*2)):
        if S[i]==S[i+p] or S[i+p]==S[i+2*p] or S[i]==S[i+2*p]:
            continue
        else:
            error+=1
d=r*g*b

print(d-error)
### BUGGY CODE ###

import copy

s = list(input())
s2 = copy.deepcopy(s)

thanS = s[0]
count = 1
a = []
for i in range(1, len(s)):
    if thanS == s[i]:
        count += 1

    else:
        thanS = s[i]
        if count == 1:
            a.append(s2[0: 1])
            del s2[0: 1]
        else:
            a.append(s2[0: count])
            del s2[0:count]
        count = 1

a.append(s2)
del s2
b = [0]

for i in range(len(a)):
    c = a[i]

    if c[0] == "<":
        add = [b[-1] + 1 + j for j in range(len(c))]
        b = b + add
    else:
        diff = len(c)
        if b[-1] <= diff:
            b[-1] = diff
            b = b + [diff - j for j in range(1, diff + 1)]
        else:
            b = b + [diff - j for j in range(1, diff + 1)]

print(sum(b))


### FIXED CODE ###

s = input()

index = 0
thanS = s[0]
count = 1
a = []
for i in range(1, len(s)):
    if thanS == s[i]:
        count += 1

    else:
        a.append(s[index: index + count])
        thanS = s[i]
        index = index + count
        count = 1

a.append(s[index:])
b = 0
add = 0

for i in range(len(a)):
    diff = len(a[i])
    if a[i][0] == "<":
        add += diff * (diff + 1) / 2
        b = diff
    else:
        if b < diff:
            add = add + diff * (diff + 1) / 2 - b
        else:
            add = add + (diff - 1) * diff / 2
        b = 0

print(int(add))
### BUGGY CODE ###

n=int(input())
s=input()
ans=100000
for i in range(len(s)):
    e=s[i+1:].count('E')
    w=s[:i].count('W')
    aa=e+w
    ans=min(ans,aa)
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
cnt=S.count("E")
m=cnt
for i in S:
    if i=="E":
        cnt-=1
    else:
        cnt+=1
    m=min(m,cnt)
print(m)
### BUGGY CODE ###

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

ans = 1
for i in range(1,m//n+1):
    rest = m - (i * (n - 1))
    if rest % i == 0:
        ans = i

print(ans)

### FIXED CODE ###

import sys
n,m = map(int,input().split())

ans = 1
for i in range(m//n,0,-1):
    rest = m - (i * (n - 1))
    if rest % i == 0:
        print(i)
        sys.exit()
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    DP = [[] for _ in range(n)]
    DP[1].append(0)
    M = 1
    for i in range(1,n):
        m = M
        flg = 0
        while m>0:
            for p in DP[m]:
                if abs(a[i]-a[p])<=k:
                    DP[m+1].append(i)
                    flg = 1
                    if m+1>M:
                        M=m+1
                    break
            if flg==1:
                break
            m -= 1
        if flg==0:
            DP[1].append(i)
    print(M)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    DP = [[] for _ in range(n)]
    DP[1].append(0)
    M = 1
    for i in range(1,n):
        m = M
        flg = 0
        while m>0:
            for p in DP[m]:
                if abs(a[i]-a[p])<=k:
                    DP[m+1].append(i)
                    flg = 1
                    if m+1>M:
                        M=m+1
                    break
            if flg==1:
                break
            m -= 1
        if flg==0:
            DP[1].append(i)
    print(M)

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

import sys

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	count=0
	for i in range(1, min(n, k)+1):
		#pa(i)
		aa=sum(aal[:i])
		if aa % k == i:
			count+=1
		for j in range(n-i):
			aa += aal[i+j]
			aa -= aal[j]
			count+=(aa % k == i)
	
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
from collections import defaultdict

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si%k
	
	count=0
	mkl_dict=defaultdict(lambda :0)
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			mkl_dict[sss[j-k]]-=1
		count += mkl_dict[sj]
		mkl_dict[sj] += 1
			
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

n,m=(int(i) for i in input().split())
p = int(m/n)
while p>1:
    if m%p==0:
        break
    p-=1
print(p)

### FIXED CODE ###

n,m=(int(i) for i in input().split())
p = int(m**(1/2))
divisors = []
for i in range(1,p+1):
    if m%i == 0:
        if n*i<=m:
            divisors.append(i)
        if n<=i:
            divisors.append(int(m/i))
print(max(divisors))
### BUGGY CODE ###

n,k=map(int,input().split())
step=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  cost=min([dp[j] + abs(step[i]-step[j]) for j in range(max(i-k,0),i)])
  dp[i]=cost
print(dp[n-1])

### FIXED CODE ###

def solve():
  n,k=[int(i) for i in input().split()]
  step=[int(i) for i in input().split()]
  dp=[0]*n
  for i in range(1,n):
    dp[i]=min([dp[j] + abs(step[i]-step[j]) for j in range(max(i-k,0),i)])
  return dp[n-1]
print(solve())
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N = int(input())
    A = input_nums()
    idx = [i for i in range(1, N+1)]
    A = dict(zip(idx, A))
    B = dict(zip(idx,[0]*N))
    A_keys = A.keys()
    for i in reversed(range(1,N+1)):
        b = i
        cnt = 0
        while True:
            if not b in A_keys:
                break
            else:
                cnt += B[b]
            b += b
        if not cnt % 2 == A[i]:
            B[i] = 1
    ans = []
    for k, v in B.items():
        if v == 1:
            ans.append(k)
    print(len(ans))
    if len(ans) != 0:
        print(*ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N = int(input())
    A = input_nums()
    idx = [i for i in range(1, N+1)]
    A = dict(zip(idx, A))
    B = dict(zip(idx,[0]*N))
    for i in reversed(range(1,N+1)):
        b = i
        cnt = 0
        while b <= N:
            cnt += B[b]
            b += i
        if not cnt % 2 == A[i]:
            B[i] = 1
        else:
            B[i] = 0
    ans = []
    for k, v in B.items():
        if v == 1:
            ans.append(k)
    print(len(ans))
    if len(ans) != 0:
        print(*ans)

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

MAX_A = 10**6 + 1

# 素数と個数を求める
def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p, c in factorize(a):
            C[p] += 1
            max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')


### FIXED CODE ###

n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')
### BUGGY CODE ###

#D
n = int(input())
l = list(map(int,input().split()))
cnt = 0
l.sort(reverse=True)



for i in range(len(l)-2):
    for j in range(i+1,len(l)-1):
        x = l[i]-l[j]
        right = n-1
        left = j
 
        while left <= right:
            mid = (right + left) //2
            if l[mid] == x:
                mid -= 1
                break
                
        
            elif l[mid] > x:
                left = mid+1
            elif l[mid] < x:
                right = mid-1
        if (mid - j) > 0:
            cnt += mid - j
 
        
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
cnt = 0
l.sort()

for i in range(n):
    for j in range(i+1,n):
        k = bisect.bisect_left(l,l[i]+l[j])
        if k > j:
            cnt += k - j - 1
        else:
            pass
            
print(cnt)
### BUGGY CODE ###

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

dictS={}
dictS[0]=1

for n in range (1,N):
    if n<K:
        # S.append(A[n]*S[-1])
        dictS[n]=A[n]*dictS[n-1]
    else:
        # S.append(A[n]*S[-1]/A[n-K])
        dictS[n]=A[n]*dictS[n-1]/A[n-K]

    if n>=K:
        if dictS[n]>dictS[n-1]:
            print('Yes')
        else:
            print('No')


### FIXED CODE ###

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

for i in range (K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

INF = 10**9

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()] + [0]*100

dp = [INF] * 100200
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))

print(dp[N-1])

### FIXED CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

INF = 10**9

dp = [INF]*100010

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i < N-j: dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])
### BUGGY CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))

cnt_list = [int_list.count(i) for i in range(1, N+1)]
ret_list = []

# これはO(N)でいける

# tmp_ans = 0
# for i in range(N):
#     if cnt_list[i] > 1:
#         tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2

tmp_ans = sum([cnt_list[i]*(cnt_list[i]-1) // 2 for i in range(N) if cnt_list[i] > 1])

# for i in range(N):
#     if cnt_list[i] < 1:
#         tmp_ret = 0
#     else:
#         tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
#     ret_list.append(tmp_ret)

# for i in int_list:
#     print(ret_list[i-1])

ret_list = [0 if cnt_list[i] < 1 else tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2 for i in range(N)]

[print(ret_list[i-1]) for i in int_list]

### FIXED CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))
cnt_list = [0] * N

for i in int_list:
    cnt_list[i-1] += 1

ret_list = [0] * N

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] > 1:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2


for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list[i] = tmp_ret

for i in int_list:
    print(ret_list[i-1])