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

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

M = t * 2 + d + m
D = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP[t][d][m] = 1
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t, -1, -1):
    for k in range(M, -1, -1):
      x = DP[i][j][k]
      y = D[i][j][k]
      if x != 0:
        if i + j + k != 0:
          su += y * N /(i + j + k)
        if i >= 1:
          DP[i - 1][j + 1][k] += x
          D[i - 1][j + 1][k] += y * i / (i + j + k)
        if j >= 1: 
          DP[i][j - 1][k + 1] += x
          D[i][j - 1][k + 1] += y * j / (i + j + k)
        if k >= 1:
          DP[i][j][k - 1] += x
          D[i][j][k - 1] += y * k / (i + j + k)

print(su)


### FIXED CODE ###

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(N - i - j, -1, -1):
      y = D[i][j][k]
      if i + j + k != 0:
        su += y * N /(i + j + k)
      if i >= 1:
        D[i - 1][j + 1][k] += y * i / (i + j + k)
      if j >= 1: 
        D[i][j - 1][k + 1] += y * j / (i + j + k)
      if k >= 1:
        D[i][j][k - 1] += y * k / (i + j + k)

print(su)
### BUGGY CODE ###

from collections import deque
import sys
#input=sys.stdin.readline
H,W=map(int,input().split())
maze=[list(input()) for i in range(H)]

#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        for j in range(W) :
            if maze[i][j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :                             #forではなく各if構文だと通った…
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())


### FIXED CODE ###

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


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())
### BUGGY CODE ###

import itertools
import numpy as np
N=int(input())
retu=[i for i in range(N)]
XY=[]
for i in range(N):
    x=list(map(int,input().split()))
    XY.append(x)
XY=np.array(XY)
permi=list(itertools.permutations(retu))
goukei=0
count=0
for i in permi:
    count+=1
    for k in range(1,N):
        goukei+=np.linalg.norm(XY[i[k-1]]-XY[i[k]])
print(goukei/count)

### FIXED CODE ###

import itertools
import numpy as np
N=int(input())
retu=[i for i in range(N)]
XY=[]
for i in range(N):
    x=list(map(int,input().split()))
    XY.append(x)
permi=list(itertools.permutations(retu))
goukei=0
count=0
for i in permi:
    count+=1
    for k in range(1,N):
        a=XY[i[k - 1]][0]- XY[i[k]][0]
        b=XY[i[k - 1]][1]- XY[i[k]][1]
        goukei+=(a**2+b**2)**0.5
print(goukei/count)
### BUGGY CODE ###

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

# import functools
# import operator
# prod = functools.partial(functools.reduce, operator.mul)

# i=K+1の時、直近K回の期末テストの点数
# p_K = prod(A[:K])
p_K = 1
for i in range(K):
    p_K *= A[i]

for i in range(K, N):
    p_Kp1 = p_K / A[i-K] * A[i]
    if p_K < p_Kp1:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

# import functools
# import operator
# prod = functools.partial(functools.reduce, operator.mul)

# i=K+1の時、直近K回の期末テストの点数
# p_K = prod(A[:K])
p_K = 1

for i in range(K, N):
    t = A[i] / A[i-K]
    p_Kp1 = p_K * t
    if p_K < p_Kp1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat.append((h, w, 0))
    dp[h] = dpr

def search(dp, mat, nH, nW, cnt):
    if dp[nH][nW] < 0:
        mat.append((nH, nW, cnt+1))
        dp[nH][nW] = cnt+1

while len(mat) > 0:
    h, w, cnt = mat.popleft()

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

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

import heapq

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]
z = tmp[2]
k = tmp[3]
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

#log = [[[False for _ in range(z)] for _ in range(y)] for _ in range(x)]
log = [[[False] * z for _ in range(y)] for _ in range(x)]
cnt = 0
h = []
heapq.heappush(h, (-(a[0]+b[0]+c[0]), 0, 0, 0))
for i in range(k): 
  tmp = heapq.heappop(h)
  print(-tmp[0])
  if tmp[1]+1 < x and log[tmp[1]+1][tmp[2]][tmp[3]] == False:
    heapq.heappush(h, (-(a[tmp[1]+1]+b[tmp[2]]+c[tmp[3]]), tmp[1]+1, tmp[2], tmp[3]))
    log[tmp[1]+1][tmp[2]][tmp[3]] = True
  if tmp[2]+1 < y and log[tmp[1]][tmp[2]+1][tmp[3]] == False:
    heapq.heappush(h, (-(a[tmp[1]]+b[tmp[2]+1]+c[tmp[3]]), tmp[1], tmp[2]+1, tmp[3]))
    log[tmp[1]][tmp[2]+1][tmp[3]] = True
  if tmp[3]+1 < z and log[tmp[1]][tmp[2]][tmp[3]+1] == False:
    heapq.heappush(h, (-(a[tmp[1]]+b[tmp[2]]+c[tmp[3]+1]), tmp[1], tmp[2], tmp[3]+1))
    log[tmp[1]][tmp[2]][tmp[3]+1] = True

### FIXED CODE ###

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]
z = tmp[2]
k = tmp[3]
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ansl = []
for p in range(x):
  if p > k:
    break
  for q in range(y):
    if p * q > k:
      break
    for r in range(z):
      if p * q * r > k:
        break
      ansl.append(a[p] + b[q] + c[r])

ansl.sort(reverse=True)

for i in range(k):
  print(ansl[i])
### BUGGY CODE ###

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

prod = 1

for i in range(n):
  prod = prod * a[i]

if prod > 10**18:
  print("-1")
else:
  print(prod)

### FIXED CODE ###

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

prod = 1
frg_overflow = False

if 0 in a:
  print(0)
else:
  for i in range(n):
    if prod <= 10**18:
      prod = prod * a[i]
    else:
      frg_overflow = True
  if frg_overflow == True:
    print(-1)
  elif prod > 10**18:
    print(-1)
  else:
    print(prod)
### BUGGY CODE ###

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

# -------- #

data = int(input())
ng_flag = False
min_value = 9999999

if is_prime(data):
    print(data -1)
    exit(0)

for i in range(1, int(data / 2) + 1):
    if data % i == 0:
        validation = i + data / i
        if validation < min_value:
            min_value = validation
print(int(min_value-2))

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

min_value = 1000000000000
data = int(input())
ng_flag = False
divisors_array = make_divisors(data)

if len(divisors_array) % 2 == 1:
    divisors_array.append(divisors_array[len(divisors_array)-1])
for i in range(0, len(divisors_array)):
    if(i % 2 == 0):
        first = divisors_array[i] -1 
        second = divisors_array[i+1] -1 
        if first + second < min_value:
            if i == 1:
                min_value = first + second
            else:
                min_value = first + second
print(min_value)
### BUGGY CODE ###

import sys

for line in sys.stdin:
	i = 5
	lis = [2,3]
	while i <= int(line):
		if i % 3 != 0:
			j = 5
			while j <= int(i**0.5):
				if j % 3 != 0:
					if i % j == 0:
						break
				j += 2
			else:
				lis.append(i)
		i += 2
	print len(lis)

### FIXED CODE ###

import sys
N = 999999
lis = []
if N >= 2:
	lis.append(2)
if  N >= 3:
	lis.append(3)
if N >= 5:
	for i in xrange(5,N+1,2):
		for item in lis:
			if item > (i**0.5):
				lis.append(i)
				break
			if i % item == 0:
				break
		else:
			lis.append(i)
dp = [0]*999999
for item in lis:
	dp[item-1] += 1
for i in xrange(1,999999):
	dp[i] += dp[i-1]

for line in sys.stdin:
	num = int(line)
	print dp[num-1]
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
Z = []
ope = []
for _ in range(M):
  ope.append(list(map(int, input().split())))
ope.sort(key=lambda x:x[1], reverse=True)
pk = np.array(ope)
totalB = sum(pk[:, 0])

while int(len(Z)) < min(N, totalB):
  for o in ope:
    for _ in range(o[0]):
      Z.append(o[1])

for i in range(min(N, len(Z))):
  if Z[i] > A[i]:
      A[i] = Z[i]
  else:
    break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
pool = []
[pool.append((a, 1)) for a in A]
for _ in range(M):
  b, c = (map(int, input().split()))
  pool.append((c, b))
pool.sort(reverse=True, key=lambda x:x[0])

while N>0:
  for p in pool:
    if p[1] >= N:
      ans += p[0]*N
      N = 0
    if p[1] < N:
      ans += p[0]*p[1]
      N -= p[1]

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

A, B, Q = list(map(int, raw_input().split()))

jinja = list()
for a in xrange(A): jinja.append(long(raw_input()))
tera = list()
for b in xrange(B): tera.append(long(raw_input()))

max_val = 10000000000000000.0

for q in xrange(Q):
    question = long(raw_input())
    if jinja[0] >= question:
        min_jinja = max_val
        max_jinja = jinja[0] - question
    elif jinja[-1] <= question:
        min_jinja = question - jinja[-1]
        max_jinja = max_val
    else:
        for a in xrange(A-1):
            if jinja[a] <= question and jinja[a+1] >= question:
                min_jinja = question - jinja[a]
                max_jinja = jinja[a+1] - question
    if tera[0] >= question:
        min_tera = max_val
        max_tera = tera[0] - question
    elif tera[-1] <= question:
        min_tera = question - tera[-1]
        max_tera = max_val
    else:
        for b in xrange(B-1):
            if tera[b] <= question and tera[b+1] >= question:
                min_tera = question - tera[b]
                max_tera =  tera[b+1] - question

    if max_tera == max_val and max_jinja == max_val:
        if min_jinja >= min_tera: print min_jinja
        else: print min_tera
    elif min_tera == max_val and min_jinja == max_val:
        if max_jinja >= max_tera: print max_jinja
        else: print max_tera
    elif min_jinja > min_tera and max_tera < max_jinja:
        if min_jinja >= max_jinja: print max_jinja
        else: print min_jinja
    elif min_tera < min_jinja and min_jinja < max_tera:
        if min_tera >= max_tera: print max_tera
        else: print min_tera
    elif min_tera <= min_jinja:
        print min(min_jinja, min_tera*2 + max_jinja, min_tera + max_jinja*2, max_tera)
    elif min_jinja <= min_tera:
        print min(min_tera, min_jinja*2 + max_tera, min_jinja + max_tera*2, max_jinja)

### FIXED CODE ###

import bisect

A, B, Q = list(map(int, raw_input().split()))

max_val = 10.0 ** 15

jinja = list()
jinja.append(-max_val)
for a in xrange(A): jinja.append(long(raw_input()))
jinja.append(max_val)
tera = list()
tera.append(-max_val)
for b in xrange(B): tera.append(long(raw_input()))
tera.append(max_val)

for q in xrange(Q):
    question = long(raw_input())
    idx_tera, idx_jinja = bisect.bisect_right(tera, question), bisect.bisect_right(jinja, question)

    cost = max_val
    for T in [tera[idx_tera-1], tera[idx_tera]]:
        for S in [jinja[idx_jinja-1], jinja[idx_jinja]]:
            d_T = abs(T - question) + abs(S - T) # pattern1: question -> T -> S
            d_S = abs(S - question) + abs(T - S) # pattern2: question -> S -> T
            cost = min(cost, d_T, d_S)
    print cost
### BUGGY CODE ###

import itertools
import re
n = int(input())
s = input()
ans = 0
for i in itertools.product(range(10),repeat=3):
    if re.search('{}.*{}.*{}'.format(i[0],i[1],i[2]), s):
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    idx = 0
    target = key[idx]
    for ii in s:
        if target == ii:
            idx += 1
            if idx > 2:
                ans += 1
                break
            target = key[idx]
print(ans)
### BUGGY CODE ###

n=int(input())
a=tuple(map(int,input().split()))
b=[0]*n
x=0
for i in set(a):
  b[i-1]=a.count(i)
  x+=(b[i-1]*(b[i-1]-1))//2
for i in a:
  y=b[i-1]-1
  print(x-y if x>=y else 0)

### FIXED CODE ###

def main():
  from collections import Counter
  n=int(input())
  a,b=tuple(map(int,input().split())),[0]*n
  c=Counter(a)
  x=0
  for i in set(a):
    b[i-1]=c[i]
    x+=(b[i-1]*(b[i-1]-1))//2
  b=tuple(b)
  for i in a:
    y=b[i-1]-1
    print(x-y if x>=y else 0)
if __name__=='__main__':
  main()
### BUGGY CODE ###

from heapq import heappush,heappop
h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx-=1
sy-=1
gx,gy=map(int,input().split())
gx-=1
gy-=1
g=[list(input()) for _ in range(h)]
v=[[0 for j in range(w)] for i in range(h)]
v2=[[0 for j in range(w)] for i in range(h)]
q=[]
heappush(q,[0,sx,sy])
while q:
    c,x,y=heappop(q)
    if x==gx and y==gy:
        print(c)
        exit()
    if v[x][y]==1:
        continue
    v[x][y]=1
    for a in range(-2,3):
        for b in range(-2,3):
            if a==b==0:
                continue
            if a*b==0 and abs(a+b)==1:
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                    heappush(q,[c,nx,ny])
                continue
            nx=x+a
            ny=y+b
            if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0 and v2[nx][ny]==0:
                heappush(q,[c+1,nx,ny])
                v2[nx][ny]=1
print(-1)

### FIXED CODE ###

from collections import deque
def main():
    h,w=map(int,input().split())
    sx,sy=map(int,input().split())
    sx-=1
    sy-=1
    gx,gy=map(int,input().split())
    gx-=1
    gy-=1
    g=[tuple(input()) for _ in range(h)]
    v=[[0 for j in range(w)] for i in range(h)]
    q=deque([[sx,sy]])
    v[sx][sy]=1
    ans=0
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    while True:
        l=[]
        while q:
            x,y=q.popleft()
            l.append([x,y])
            if x==gx and y==gy:
                print(ans)
                exit()
            for a,b in k:
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                    q.append([nx,ny])
                    v[nx][ny]=1
        if len(l)==0:
            break
        for x,y in l:              
            for a in range(-2,3):
                for b in range(-2,3):
                    if a*b==0 and abs(a+b)<=1:
                        continue
                    nx=x+a
                    ny=y+b
                    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                        q.append([nx,ny])
                        v[nx][ny]=1
        ans+=1 
    print(-1)
if __name__=='__main__':
    main()
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

ans = 0

for i in range(N - 2):
  for j in range(N - i - 2):
    if S[i] == S[i + j + 1]:
      continue
    for k in range(N - i - j - 2):
      if S[i + j + 1] != S[i + j + k + 2] and S[i + j + k + 2] != S[i] and j != k:
        ans += 1

print(ans)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

R = S.count("R")
G = S.count("G")
B = S.count("B")

cnt = 0

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = i + ((j - i) * 2)
    if k < N:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        cnt += 1

print(R * G * B - cnt)
### BUGGY CODE ###

# n,k=map(int,input().split())
n=int(input())
l=list(map(int,input().split()))
for i in range(1,n+1):
  print(l.index(i)+1,end=" ")

### FIXED CODE ###

# n,k=map(int,input().split())
n=int(input())
l=list(map(int,input().split()))
fi=[]
for i in range(n):
  ll=[]
  ll.append(l[i])
  ll.append(i+1)
  fi.append(ll)
fi.sort()
for i in fi:
  print(i[1],end=" ")
### BUGGY CODE ###

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

def xor_(x, y):
    p, q = list(sorted([x, y]))
    p = bin(p)
    q = bin(q)

    i = -1
    r = str()
    while p[i] != 'b':
        if p[i] == q[i]:
            r = '0' + r
        else:
            r = '1' + r
        i -= 1

    while q[i] != 'b':
        r = q[i] + r
        i -= 1
    
    r = '0b' + r

    return(int(r, 0))

sum = 0
for i in range(n-1):
    for j in range(i+1, n):
        sum += xor_(a[i], a[j])
        sum = sum % (10**9 + 7)

print(sum)


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    ret = 0
    magni = 1
    for j in range(60):
        bin_cnt = [0, 0]
        for i in range(n):
            a[i], b = divmod(a[i], 2)
            bin_cnt[b] += 1
        x, y = bin_cnt
        ret += x * y * magni % mod
        magni = magni * 2 % mod

    ret %= mod

    print(ret)


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

H,N=map(int,input().split())
L=[tuple(map(int,input().split())) for i in range(N)]
dp=[[-1]*(H+1) for i in range(N+1)]
for d in dp:
    d[0]=0
dp[0]=[10**9]*(H+1)
i=1
for a,b in L:
    for j in range(H+1):
        if j<a:
            dp[i][j]=min(dp[i-1][j],b)
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-a]+b)
    i+=1
print(dp[N][H-1])

### FIXED CODE ###

H,N=map(int,input().split())
L=[tuple(map(int,input().split())) for i in range(N)]
dp=[[-1]*(H+1) for i in range(N+1)]
for d in dp:
    d[0]=0
dp[0]=[10**9]*(H+1)
i=1
for a,b in L:
    for j in range(H+1):
        if j<a:
            dp[i][j]=min(dp[i-1][j],b)
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-a]+b)
    i+=1
print(dp[N][H-1])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

dic1 = dict()

for i in lst1:
    if i in dic1:
        dic1[i] += 1
    else:
        dic1[i] = 1

values = list(dic1.values())

values.sort()

ans = 0
while k < len(values):
    ans += values.pop(0)

print(ans)


### FIXED CODE ###

import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

dic1 = dict()

for i in lst1:
    if i in dic1:
        dic1[i] += 1
    else:
        dic1[i] = 1

values = list(dic1.values())

values.sort()

values = deque(values)

ans = 0
while k < len(values):
    ans += values.popleft()

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

import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
cnt = [0] * (n + 1)
for item in a:
    cnt[item] += 1
cnt.sort()
cumsum = [0] * (n + 2)
for i in range(n+1):
    cumsum[i+1] = cumsum[i] + cnt[i]

ans = []
for i in range(n):
    if cnt[i+1] == 0:
        ans.append(0)
        continue
    l = 0; r = n+1
    while r - l > 1:
        mid = (l + r) // 2
        index = bisect.bisect_left(cnt, mid) - 1
        if index <= i:
            l = mid
            continue
        num = index - i
        if mid * num <= cumsum[index + 1]:
            l = mid
        else:
            r = mid
    ans.append(l)

ans.reverse()
print("\n".join([str(item) for item in ans]))

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
cnt = [0] * (n + 1)
for item in a:
    cnt[item] += 1
cnt.sort()
cumsum = [0] * (n + 2)
for i in range(n+1):
    cumsum[i+1] = cumsum[i] + cnt[i]

indexes = [0] * (n+1)
for i in range(n+1):
    indexes[i] = bisect.bisect_left(cnt, i) - 1

ans = []
for i in range(n):
    if cnt[i+1] == 0:
        ans.append(0)
        continue
    l = 0; r = n+1
    while r - l > 1:
        mid = (l + r) // 2
        index = indexes[mid]
        if index <= i:
            l = mid
            continue
        num = index - i
        if mid * num <= cumsum[index + 1]:
            l = mid
        else:
            r = mid
    ans.append(l)

ans.reverse()
print("\n".join([str(item) for item in ans]))
### BUGGY CODE ###

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


dic = {}
for t in A:
    dic[t] = A.count(t)

ans_dict = {}
for i in list(dic.keys()):
    ans = 0
    for key in list(dic.keys()):
        val = dic.get(key)
        if i == key:
            val -= 1
        ans += val * (val - 1) // 2
    ans_dict[i] = ans

# print(ans_dict)

for i in range(N):
    print(ans_dict.get(A[i]))

### FIXED CODE ###

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

dic = {}
ans = 0
# for t in A:
#     if t in dic.keys():
#         continue
#     tmp = A.count(t)
#     dic[t] = tmp
#     ans += tmp*(tmp-1)//2

for a in A:
    tmp = dic.get(a)
    if tmp == None:
        dic[a] = 1
    else:
        dic[a] = tmp + 1

for key in list(dic.keys()):
    tmp = dic.get(key)
    ans += tmp * (tmp - 1) // 2
    

for a in A:
    val = dic.get(a)
    print(ans-val+1)