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

from collections import deque
n,k = map(int, input().split())
a = [0]+list(map(int, input().split()))

genzaiti=1
imamade=deque([1])
hantei=True

while k>0:
    k-=1
    genzaiti=a[genzaiti]

    if hantei:
        for i in range(len(imamade)):
            if imamade[i]==genzaiti:
                kaiten=len(imamade)-i
                k%=kaiten
                hantei=False
                break
    
    imamade.append(genzaiti)

print(genzaiti)

### FIXED CODE ###

from collections import deque
n,k = map(int, input().split())
a = [0]+list(map(int, input().split()))

genzaiti=1
otozure=[-1]*(10**6)
hantei=True

otozure[1]=0
houmon=0
idou_kaisuu=0

while k>0:
    idou_kaisuu+=1
    k-=1
    genzaiti=a[genzaiti]

    if hantei:
        if otozure[genzaiti]!=-1:
            kaiten=idou_kaisuu-otozure[genzaiti]
            k%=kaiten
            hantei=False
    
    otozure[genzaiti]=idou_kaisuu

print(genzaiti)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(x[0],x[1]))

b = []
for i in range(N):
  b.append([-a[i][1], a[i][0]])

from bisect import bisect_left, bisect_right
import heapq

ans = 0
h = []

for i in range(1,M+1):
  left = bisect_left(a,[i,0])
  right = bisect_right(a,[i,float('inf')])-1
  if right-left>=0:
    for i in range(left,right+1):
      heapq.heappush(h,b[i])
    x = heapq.heappop(h)
    ans += -x[0]
  else:
    if h:
      x = heapq.heappop(h)
      ans += -x[0]

print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(x[0],x[1]))

b = []
for i in range(N):
  b.append([-a[i][1], a[i][0]])

from bisect import bisect_left, bisect_right
import heapq

ans = 0
h = []

for i in range(1,M+1):
  left = bisect_left(a,[i,0])
  right = bisect_right(a,[i,float('inf')])-1
  if right-left>=0:
    for i in range(left,right+1):
      heapq.heappush(h,b[i])
    x = heapq.heappop(h)
    ans += -x[0]
  else:
    if h:
      x = heapq.heappop(h)
      ans += -x[0]

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

H, W=map(int, input().split())

m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for i in range(W)]+[-1] for j in range(H)]
m=m+mm+m

nexts=[]
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      nexts.append([i, j])
      m[i][j]=1
      
def f(math, in_nexts):
  n=len(in_nexts)
  out_nexts=[]
  for i in range(n):
    x=in_nexts[i][0]
    y=in_nexts[i][1]
    if math[x-1][y]==0:
      math[x-1][y]=math[x][y]+1
      out_nexts.append([x-1, y])
    if math[x+1][y]==0:
      math[x+1][y]=math[x][y]+1
      out_nexts.append([x+1, y])
    if math[x][y-1]==0:
      math[x][y-1]=math[x][y]+1
      out_nexts.append([x, y-1])
    if math[x][y+1]==0:
      math[x][y+1]=math[x][y]+1
      out_nexts.append([x, y+1])
      
  return math, out_nexts

counter=0
while len(nexts)>0:
  m, nexts=f(m, nexts)
  counter+=1
  
print(counter-1)

### FIXED CODE ###

H, W=map(int, input().split())

m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for i in range(W)]+[-1] for j in range(H)]
m=m+mm+m

nexts=[]
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      nexts.append([i, j])
      m[i][j]=1
      
def f(math, in_nexts):
  n=len(in_nexts)
  out_nexts=[]
  for i in range(n):
    x=in_nexts[i][0]
    y=in_nexts[i][1]
    if math[x-1][y]==0:
      math[x-1][y]=math[x][y]+1
      out_nexts.append([x-1, y])
    if math[x+1][y]==0:
      math[x+1][y]=math[x][y]+1
      out_nexts.append([x+1, y])
    if math[x][y-1]==0:
      math[x][y-1]=math[x][y]+1
      out_nexts.append([x, y-1])
    if math[x][y+1]==0:
      math[x][y+1]=math[x][y]+1
      out_nexts.append([x, y+1])
      
  return math, out_nexts

counter=0
while len(nexts)>0:
  m, nexts=f(m, nexts)
  counter+=1
  
print(counter-1)
### BUGGY CODE ###

def check(n,p):
    for i in range(n):
        if (i+1) == p[i]:
            return False
    return True

def solve(n,p):
    
    memo = {}
    items = [(0,p)]
    result = 0
    while items:
        step, p = items.pop(0)
        if check(n,p):
            result = step
            break
        else:
            for i in range(n-1):
                candidate = tuple( p[:i] +[ p[i+1] ,p[i]] + p[i+2:] )
                if not candidate in memo:
                    items.append([step +1 , list(candidate)])
                    memo[candidate] = step + 1
                
    return result

if __name__ == '__main__':
    n = int(input())
    p = list(map(int, input().split(" ")))
    print(solve(n, p))


### FIXED CODE ###

def solve(n, p):
    result = 0
    for i in range(n-1):
        if (i+1) == p[i]:
            p[i], p[i+1] = p[i+1],p[i]
            result += 1
    i = n - 1
    if (i+1) == p[i]:
        p[i-1], p[i] = p[i],p[i-1]
        result += 1
    return result

if __name__ == '__main__':
    n = int(input())
    p = list(map(int, input().split(" ")))
    print(solve(n, p))
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
result = []
for i in range(k):
    left = one_index - i
    right = len(nums[one_index+1:]) + i
    if left < 0 or right < 0:
        continue
    else:
        result.append(math.ceil(left/(k-1))+math.ceil(right/(k-1)))
print(min(result))


### FIXED CODE ###

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
if k == len(nums):
    print(1)
else:
    print(math.ceil((n-1)/(k-1)))
### BUGGY CODE ###

n, k = list(map(int,input().split()))
jump = list(map(int,input().split()))
arr = list(map(int,input().split()))
best = - (10**28)
VV = []
 
for i in range(n):
  if i not in VV:
    order = []
    prev_pos = i
    visited = []
    sub_best = 0
    order = []
    l = 0
 
    for jjj in range(n):
      order.append(arr[prev_pos])
      #sub_best = max(sub_best, sum(order))
      visited.append(prev_pos)
      VV.append(prev_pos)
      l += 1
 
      next_pos = jump[prev_pos] - 1
      prev_pos = next_pos
      if next_pos in visited:
        break
 
    if sum(order)<1:
      limit = min(k,l*2)
      ss = 0
    else:
      limit = (k % l) + l
      limit = min(k,limit)
      ss = sum(order) * ((k//l) - 1)
 
    sub_best += ss
    #print(limit)
    
    order = order + order + order
    
    for op in range(len(order)):
      for chuj in range(1,limit+1):
        kk = sum(order[op:op+chuj])
        best = max(best, sub_best + kk)
      
print(best)

### FIXED CODE ###

n, k = list(map(int,input().split()))
jump = list(map(int,input().split()))
arr = list(map(int,input().split()))
best = - (10**28)
VV = []
 
for i in range(n):
  if i not in VV:
    order = []
    prev_pos = i
    visited = []
    sub_best = 0
    order = []
    l = 0
 
    for jjj in range(n):
      order.append(arr[prev_pos])
      #sub_best = max(sub_best, sum(order))
      visited.append(prev_pos)
      VV.append(prev_pos)
      l += 1
 
      next_pos = jump[prev_pos] - 1
      prev_pos = next_pos
      if next_pos in visited:
        break
 
    if sum(order)<1:
      limit = min(k,l*2)
      ss = 0
    else:
      limit = (k % l) + l
      limit = min(k,limit)
      ss = sum(order) * ((k//l) - 1)
      ss = max(ss,0) 
 
    sub_best = ss
   # print(limit, order, ss, sub_best)
    
    order = order + order + order
    
    for chuj in range(1,limit+1):
      kk = sum(order[0:0+chuj])
      best = max(best, sub_best + kk)
      for op in range(len(order)-chuj):
        kk -= order[op]
        kk += order[op+chuj]
        best = max(best, sub_best + kk)
      
print(best)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
last = [n]*n
for i in range(k):
    temp = [0]*n
    min_a = 10**10
    for j in range(n):
        b = a[j]
        min_a = min(b, min_a)
        temp[j] += 1
        for k in range(1, b + 1):
            if j + k < n:
                temp[j + k] += 1
            if j - k >= 0:
                temp[j - k] += 1
    a = temp[:]
    if min_a == n:
        print(*a)
        sys.exit()
print(*a)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
from itertools import accumulate
for i in range(k):
    temp = [0]*(n + 1)
    for j in range(n):
        b = a[j]
        left = max(0, j - b)
        right = min(n - 1, j + b)
        temp[left] += 1
        temp[right + 1] -= 1
    a = list(accumulate(temp))[:n]
    if min(a) == n:
        print(*a)
        sys.exit()
print(*a)
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().strip().split())
    c = list(map(int, input().strip().split()))
    mask = 0b0
    for i in c:
        mask |= 0b1 << (i - 1)

    for j in range(1 << n):
        dp[j | mask] = min(dp[j] + a, dp[j | mask])

print(dp[(1 << n) - 1] if dp[(1 << n) - 1] < float('inf') else -1)

### FIXED CODE ###

n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
x=1
for i in range(n):
	x *=a[i]
    
if x<=10**18:
	print(x)
else:
	print(-1)

### FIXED CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
a.sort()
x=1
for i in range(n):
	x *=a[i]
	if x>10**18:
		print(-1)
		sys.exit()
        
print(x)
### BUGGY CODE ###

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

import math
# N = 2
# ARR = [1000000000, 1000000000]

def calculate(n,arr):
    res = 1
    for i in range(n):
        # a1 = math.log(arr[i],10)
        # a2 = math.log(arr[i], 10)
        # if a1 + a2 > 18:
        #     res = -1
        #     continue
        res = res * arr[i]
        if res > 1000000000000000000:
            res = -1

    return res

print(calculate(N,ARR))



### FIXED CODE ###

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


# N = 3
# ARR = [1000000000, 0, 9]
#
# N = 31
# ARR =  [4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0]

def calculate(n, arr):
    res = 1
    for i in range(n):
        if arr[i] == 0:
            res = 0
            break

        if res == -1:
            continue

        res = res * arr[i]
        if res > 1000000000000000000:
            res = -1

    return res


print(calculate(N, ARR))
### BUGGY CODE ###

N, K = map(int, input().split())
A = []
for i in range(N):
    a, b = map(int, input().split())
    for k in range(b):
        A.append(a)
A.sort()
print(A[K-1])

### FIXED CODE ###

N, K = map(int, input().split())
A = [0 for _ in range(10 ** 5)]
for i in range(N):
    a, b = map(int, input().split())
    A[a - 1] += b
for i in range(10 ** 5):
    if K - A[i] > 0:
        K = K - A[i]
    else:
        print(i + 1)
        break
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
parents = [-1]*N
query = [[] for _ in range(N)]
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    query[a-1].append(b-1)

for i, c in enumerate(parents):
    if c==-1:
        root = i
        break

from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        parents[nx] = v
        Q.append(nx)

for p in parents:
    print(p+1)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
parents = [-1]*N
query = [[] for _ in range(N)]
get_into = [0]*N
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    get_into[b-1] += 1
    query[a-1].append(b-1)

for i, c in enumerate(parents):
    if c==-1:
        root = i
        break

from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        get_into[nx] -= 1
        if get_into[nx]==0:
            parents[nx] = v
            Q.append(nx)

for p in parents:
    print(p+1)
### BUGGY CODE ###

n,s=map(int,input().split()) 
a=list(map(int,input().split()))
mod=998244353
d=[[0 for l in range(s+1)] for _ in range(n+1)]
d[0][0]=1
for i in range(1,n+1):
    val=a[i-1]
    for j in range(0,s+1):
        d[i][j]+=2*d[i-1][j]
        d[i][j]%=mod
        if val<=j:
            d[i][j]+=d[i-1][j-val]
            d[i][j]%=mod
print(d[n][s])

### FIXED CODE ###

n,s=map(int,input().split()) 
a=list(map(int,input().split()))
d=[[0]*(s+1) for _ in range(n+1)]
d[0][0]=1
for j in range(0,s+1):
    for i in range(1,n+1):
        d[i][j]=2*d[i-1][j]
        if a[i-1]<=j:
            d[i][j]+=d[i-1][j-a[i-1]]
        d[i][j]=d[i][j]%998244353
print(d[n][s])
### BUGGY CODE ###

n = int(input())
h = [int(x) for x in input().split(' ')]

a = 0
for c in range(n) :
    cnt = 0
    z = h[c]
    for d in range(c+1,n) :
        if (z >= h[d]) :
            cnt += 1
            z = h[d]
        else :
            break
    if a < cnt :
        a = cnt

print(a)

### FIXED CODE ###

n = int(input())
h = [int(x) for x in input().split(' ')]

cnt = 0
a = 0
for c in range(n-1) :
    if (h[c] >= h[c+1]) :
        cnt += 1
    else :
        if a < cnt :
            a = cnt
        cnt = 0

if a < cnt :
    a = cnt


print(a)
### BUGGY CODE ###

w, x = input().split(" ")
a = int(w)
b = int(x)

min = False
i = 1
while(not min):
    if i%a == 0 and i%b == 0:
        min = True
        break
    i += 1

print(i)

### FIXED CODE ###

w, x = input().split(" ")
a = int(w)
b = int(x)

def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm

print(compute_lcm(a, b))
### BUGGY CODE ###

S=input()
ans = [0] * len(S)
for i in range(len(S)):
    if S[i] == "L":
        cnt = 0
        for j in reversed(range(i)):
            cnt += 1
            if S[j] == "R":
                break
        if cnt % 2 == 1:
            ans[j+1] += 1
        else:
            ans[j] += 1
    if S[i] == "R":
        cnt = 0
        for j in range(i+1, len(S)):
            cnt += 1
            if S[j] == "L":
                break
        if cnt %2 == 1:
            ans[j-1] += 1
        else:
            ans[j] += 1
ans = map(str, ans)
print(" ".join(ans))

### FIXED CODE ###

S=input()
ans = [0] * len(S)
last_R=[0] * len(S)
tmp = 0
for i in range(len(S)):
    if S[i] == "R":
        tmp = i
    last_R[i] = tmp
first_L=[0] * len(S)
tmp = 0
for i in reversed(range(len(S))):
    if S[i] == "L":
        tmp = i
    first_L[i] = tmp
for i in range(len(S)):
    if S[i] == "L":
        R_index = last_R[i]
        if (i - R_index) % 2 == 1:
            ans[R_index+1] += 1
        else:
            ans[R_index] += 1
    if S[i] == "R":
        L_index = first_L[i]
        if (L_index - i) %2 == 1:
            ans[L_index-1] += 1
        else:
            ans[L_index] += 1
ans = map(str, ans)
print(" ".join(ans))
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
ans="Yes"
for i in range(n-1):
 #   print((h[i+1:]))
    if h[i]-min(h[i+1:])>1.1:
        
        ans="No"
        break
    
print(ans)    

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
ans="Yes"
minh=h[n-1]

for i in range(n-1,-1,-1):
  #  print((h[i+1:]),minh)
    minh=min(minh,h[i])
    if h[i]-minh>1.1:
        ans="No"
        break
    
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

N,K = map(int,input().split())
T = [[]*N for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
visited = [0]*N
ans = 1
def bfs(i,bb,b):
    global ans
    visited[i] = 1
    ans = (ans*(K-bb-b))%(10**9+7)
    cnt = 0
    for j in T[i]:
        if visited[j] == 1:
            continue
        bfs(j,b+cnt,1)
        cnt += 1
bfs(0,0,0)
print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

N,K = map(int,input().split())
T = [[]*N for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
visited = [0]*N
ans = 1
def bfs(i,bb,b):
    global ans
    visited[i] = 1
    ans = (ans*(K-bb-b))%(10**9+7)
    cnt = 0
    for j in T[i]:
        if visited[j] == 1:
            continue
        bfs(j,b+cnt,1)
        cnt += 1
bfs(0,0,0)
print(ans)
### BUGGY CODE ###

def is_prime(n):
  t = 2
  while n > t:
    if n % t == 0: return 0
    t += 1
  return 1

c = 0
for _ in range(int(input())):
  c += is_prime(int(input()))
print(c)


### FIXED CODE ###

def is_prime(x):
  if x == 2: return 1
  if x % 2 == 0: return 0
  for i in range(3, int(x ** 0.5) + 1, 2):
    if x % i == 0: return 0
  return 1

c = 0
for _ in range(int(input())):
  c += is_prime(int(input()))
print(c)
### BUGGY CODE ###

from fractions import gcd
k = int(input())
ans = 0
for a in range(1,k+1):
	for b in range(1,k+1):
		for c in range(1,k+1):
			ans += gcd(gcd(a,b),c)

print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for a in range(1,k+1):
	for b in range(1,k+1):
		for c in range(1,k+1):
			ans += gcd(gcd(a,b),c)

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

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#V, E, r = map(int, input().split())
#INF = V * 10001
#A = [int(i) for i in input().split()]


N = int(input())
A = [int(i) for i in input().split()]
dp = [0]*(N+1)
ans = 0
a = [0]*N
minus = 0

for i in range(N):
  a[i] = A.count(A[i])
  if(a[i]<2):
    dp[A[i]] = 0
  elif(dp[A[i]] == 0):
    dp[A[i]] = combinations_count(a[i], 2)

ans = sum(dp)

#print(dp)
for i in range(N):
  temp = dp[A[i]]
  if(a[i]==2):
    minus = temp-1
  elif(a[i]<2):
    minus = temp
  else:
    minus = combinations_count(a[i]-1, 2)
  print(int(ans-(temp-minus)))

#print(ans)


### FIXED CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#V, E, r = map(int, input().split())
#INF = V * 10001
#A = [int(i) for i in input().split()]


N = int(input())
A = [int(i) for i in input().split()]
dp = [0]*(N+1)
ans = 0
cnt = 0
tle = 0

As = list(set(A))
c = Counter(A)

for i in As:
  cnt = c[i]
  if(cnt<2):
    dp[i] = 0
  else:
    dp[i] = combinations_count(cnt, 2)

tle = sum(dp)

#print(dp)
for i in range(N):
  ans = tle - (c[A[i]]-1)
  if(ans < 0):
    ans = 0
  print(int(ans))

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

def main():
    S = input()

    mod = 10**9+7
    N = len(S)
    ans = 0

    memo = {}
    for i in range(1000):
        s = str(i).zfill(3)
        memo[s] = [0 for _ in [0]*13]
        memo[s][i%13] = 1

    def rep_Q_count(s):
        memo[s] = [0 for _ in [0]*13]
        for q in range(10):
            s2 = s.replace("?",str(q),1)
            for i,n in enumerate(memo[s2]):
                memo[s][i] += n

    for i in range(100):
        s = str(i).zfill(2)
        rep_Q_count(s+"?")
        rep_Q_count(s[0]+"?"+s[1])
        rep_Q_count("?"+s)
    for i in range(10):
        s = str(i)
        rep_Q_count(s+"??")
        rep_Q_count("?"+s+"?")
        rep_Q_count("??"+s)
    rep_Q_count("???")

    s0 = S[max(0,N-3):N].zfill(3)
    dp = memo[s0][:]
    for i in range(1,(N-1)//3+1):
        s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
        j = i%2
        tmp = memo[s]
        dp2 = [0]*13
        for k,n in enumerate(tmp):
            for l,m in enumerate(dp):
                dp2[(l+k*((-1)**j))%13] += n*m
        dp = dp2
        for i in range(13):
            dp[i] %= mod
    print(dp[5])
main()

### FIXED CODE ###

S = input()

mod = 10**9+7
N = len(S)
ans = 0

memo = {}
for i in range(1000):
    s = str(i).zfill(3)
    memo[s] = [0 for _ in [0]*13]
    memo[s][i%13] = 1

def rep_Q_count(s):
    memo[s] = [0 for _ in [0]*13]
    for q in range(10):
        s2 = s.replace("?",str(q),1)
        for i,n in enumerate(memo[s2]):
            memo[s][i] += n

for i in range(100):
    s = str(i).zfill(2)
    rep_Q_count(s+"?")
    rep_Q_count(s[0]+"?"+s[1])
    rep_Q_count("?"+s)
for i in range(10):
    s = str(i)
    rep_Q_count(s+"??")
    rep_Q_count("?"+s+"?")
    rep_Q_count("??"+s)
rep_Q_count("???")

s0 = S[max(0,N-3):N].zfill(3)
dp = memo[s0][:]
for i in range(1,(N-1)//3+1):
    s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
    j = i%2
    tmp = memo[s]
    dp2 = [0]*13
    for k,n in enumerate(tmp):
        for l,m in enumerate(dp):
            dp2[(l+k*((-1)**j))%13] += n*m
    dp = dp2
    for i in range(13):
        dp[i] %= mod
print(dp[5])
### BUGGY CODE ###

N=int(input())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
MAX = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, MAX + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

buf=0
for k in range(1,N+1):
    for j in range(1,N-k+1):
        buf += (cmb(N,k,mod)*cmb(N-k,j,mod)*(8**(N-k-j)%mod))%mod
        buf = buf % mod
print(buf)


### FIXED CODE ###

N=int(input())

mod=10**9+7
def mpow(x,n):
    return x**n % mod

print((mpow(10,N) - 2 * mpow(9,N) + mpow(8,N))%mod)