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

# a < b + c
# b < a + C
# c < a + b

# 4 3 2 1
# a b c 

# abs(a - b) < c < a + b
# a < b < c
# b - a < b < c
# c < a + b 

from math import ceil, floor
from bisect import bisect_left, bisect_right

def solution(N, data): # O(N^2 * logN)
    data = sorted(data)
    c = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            c += bisect_left(data[j+1:], data[i] + data[j])

    return c

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)



### FIXED CODE ###

# a < b + c
# b < a + C
# c < a + b

# 4 3 2 1
# a b c 

# abs(a - b) < c < a + b
# a < b < c
# b - a < b < c
# c < a + b 

from math import ceil, floor
from bisect import bisect_left, bisect_right

def solution(N, data): # O(N^2 * logN)
    data.sort()
    c = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            c += bisect_left(data, data[i] + data[j], j) - j - 1

    return c

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)
### BUGGY CODE ###

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

for _ in range(q):
  query = input()
  if query[0] == "1":
    s = s[::-1]
  else:
    ti, fi, ci = query.split()
    if fi == "1":
      s = ci + s  
    else:
      s = s + ci

print(s)

### FIXED CODE ###

from collections import deque

s = input() 
s_queue = deque(s)
q = int(input())

inverted = False

for _ in range(q):
  query = input()
  if query[0] == "1":
    inverted = not inverted 
  else:
    ti, fi, ci = query.split()
    if fi == "1" and inverted:
      s_queue.append(ci)
    elif fi == "1" and not inverted:
      s_queue.appendleft(ci)
    elif fi == "2" and inverted:
      s_queue.appendleft(ci)
    else:
      s_queue.append(ci)

if inverted:
  print("".join(s_queue)[::-1])
else:
  print("".join(s_queue))
### BUGGY CODE ###

N = int(input())
L = map(int, input().split())

from itertools import combinations

comb = combinations(L, 3)

ans = 0
for c in comb:
    if 2*max(c)<sum(c):
        ans+=1
        
print(ans)

### FIXED CODE ###

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

from bisect import bisect_right

L = sorted(L, reverse=True)
L = [-L[i] for i in range(N)]

cnt=0
for i in range(N-2):
    for j in range(i+1, N-1):
        diff = L[i]-L[j]
        idx = bisect_right(L, diff-1, j+1, N)
        cnt+=(idx-j)-1
    
print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
f=lambda x:0.5*(x+1)
p=list(map(f,p))
ans=0.
for i in range(n-k+1):
    ans=max(ans,sum(p[i:i+k]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
f=lambda x:0.5*(x+1)
pp=list(map(f,p))
t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+pp[i]
ans=0
for i in range(n-k+1):
    ans=max(ans,t[i+k]-t[i])
print(ans)
### BUGGY CODE ###

nkq = input()
NKQ =nkq.split(" ")
point = []
for j in range(int(NKQ[0])): #各参加者の初期ポイント
  point.append(int(NKQ[1]))
for i in range(int(NKQ[2])):
  Ai = int(input()) - 1 #正解した参加者の番号(配列で)
  for k in range(int(NKQ[0])): #正解した参加者以外-1
    if k != Ai:
      point[k] = point[k] -1
for l in range(int(NKQ[0])):
  if point[l] <= 0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

nkq = input()
NKQ = nkq.split(" ")
point = []
for i in range(int(NKQ[0])):
  point.append(int(NKQ[1]) - int(NKQ[2])) #参加者のポイント
for j in range(int(NKQ[2])):
  Ai = int(input()) - 1
  point[Ai] = point[Ai] + 1
for k in range(int(NKQ[0])):
  if point[k] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N, M = map(int, input().split())

friend_list = []
for i in range(M):
  pair = list(map(int, input().split()))
  friend_list.append(set(pair))

group_num_people = []
for i, group in enumerate(friend_list):
  group_list = [group]
  for j, target in enumerate(friend_list):
    if i == j:
      continue
    else:
      if len(group.intersection(target)) >= 1:
        group_list.append(target)
  group_num_people.append(len(set().union(*group_list)))


if M == 0:
  print(1)
else:
  print(max(group_num_people))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class UnionFind():
    """ UnionFindはグループの分割はできないことに注意 """
    def __init__(self, n):
        """
            n: 要素数
            parents: 親を示す、-1の場合、自身の親がいない(頂点)であることを示す
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        親の要素が何かを調べる
        同じ要素であれば、同じグループに所属することを示す
        探索しながら、親を頂点につなぎ直すことで、効率的にまとめることができる
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        xとyの所属するグループをまとめる
        """
        x = self.find(x)
        y = self.find(y)

        # 同じ親だった場合、既にグループはまとまっているので処理を終了する
        if x == y:
            return

        # 浅い方を深い方に繋ぐようにする
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    def most_depth_root(self):
        return -min(self.parents)


N, M = map(int, input().split())

union_find = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)

print(union_find.most_depth_root())
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():
    input_num = int(input())
    flag = True
    sum_num = 0

    while flag:
        chushutsu = input_num % 10
        sum_num += chushutsu
        input_num = input_num // 10
        if input_num == 0:
            flag = False

    if sum_num % 9 == 0:
        print('Yes')

    else:
        print('No')

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    input_num = input()
    sum_num = 0

    for i in range(len(input_num)):
        chushutsu = int(input_num[i])
        sum_num += chushutsu
    
    if sum_num % 9 == 0:
        print('Yes')

    else:
        print('No')

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 
def main():
    s = input() 
    n = len(s)
    T = [0]
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*10**(i-1)%2019+T[i-1]%2019)%2019
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 

def main():
    s = input() 
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*pow(10, i-1, P) + T[i-1])%P
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

def exp_k(n):
    exp_list = []
    for i in range(n):
        exp = (P[i] * (P[i] + 1) / 2) / P[i]
        exp_list.append(exp)
    return exp_list

exp_max = 0
a = exp_k(n)
for i in range(n-k+1):
    exp_sum = sum(a[i:(i+k)])
    if exp_max < exp_sum:
        exp_max = exp_sum
        
print(exp_max)

### FIXED CODE ###

import itertools
N, K = map(int, input().split())
p = list(map(int, input().split()))

pos = [(p[i]+1)/2 for i in range(N)]

pos_acum = list(itertools.accumulate(pos))

ans = pos_acum[K-1]
for i in range(N-K):
    ans = max(ans, pos_acum[K+i]-pos_acum[i])
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
n,q=map(int,input().split())
a=[]
for i in range(n):
  s,t,x=map(int,input().split())
  s-=x
  t-=x
  a.append([s,t,x])
a=sorted(a,reverse=True)
heap=[]
ans=[]
for i in range(q):
  d=int(input())
  while a and a[-1][0]<=d:
    e=a.pop()
    heappush(heap,(e[2],e[1]))
  while heap and heap[0][1]<=d:
    heappop(heap)
  if heap:
    ans.append(heap[0][0])
  else:
    ans.append(-1)

print(*ans, sep='\n')



### FIXED CODE ###

import sys
from heapq import heappush, heappop
n,q=map(int,input().split())
a=sorted(((s-x, t-x, x) for _ in range(n) for s, t, x in (map(int, sys.stdin.readline().split()),)), reverse=True)
heap=[]
ans=[]
for i in range(q):
  d=int(input())
  while a and a[-1][0]<=d:
    e=a.pop()
    heappush(heap,(e[2],e[1]))
  while heap and heap[0][1]<=d:
    heappop(heap)
  if heap:
    ans.append(heap[0][0])
  else:
    ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

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

cnt = 0
for _ in range(q):
  t = input()
  if t[0] == "1":
    cnt += 1
  else:
    if cnt%2 == 1:
      s = "".join(list(reversed(s)))
      cnt = 0
    _,f,c = t.split(" ")
    if f == "1":
      s = c + s
    else:
      s = s + c
if cnt%2 == 1:
  s = "".join(list(reversed(s)))
  cnt = 0

print(s)


### FIXED CODE ###

from collections import deque
def main():
  s = deque(list(input()))
  q = int(input())
  sr = s.reverse
  sa = s.append
  sal = s.appendleft

  cnt = 0
  for _ in range(q):
    t = input()
    if t[0] == "1":
      cnt += 1
    else:
      _,f,c = t.split(" ")
      if f == "1":
        if cnt%2==1:
          sa(c)
        else:
          sal(c)
      else:
        if cnt%2==1:
          sal(c)
        else:
          sa(c)
  if cnt%2 == 1:
    sr()
  print("".join(list(s)))

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

import bisect

n = int(input())
L = sorted(list(map(int, input().split())), reverse=True)

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        S = sorted(L[j+1:])
        ans += len(S) - bisect.bisect_right(S, L[i]-L[j])

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

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

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S = S | set(range(l, r + 1))
mod = 998244353

dp = [0 for _ in range(3 * N)]
for s in S:
    dp[s + 1] = 1

S_min = min(S)
for i in range(S_min, N + 1):
    for s in S:
        dp[i] += dp[i - s]
        dp[i] %= mod
print(dp[N] % mod)

### FIXED CODE ###

N, K = map(int, input().split())
S = []
for _ in range(K):
    S.append(list(map(int, input().split())))
mod = 998244353

dp = [0 for _ in range(2 * N + 1)]
dp[1] = 1

cum = [0 for _ in range(2 * N + 1)]
cum[1] = 1

for i in range(N):
    for l, r in S:
        dp[i + 1] += cum[i - l + 1] - cum[i - r]
        dp[i + 1] %= mod
    cum[i + 1] = cum[i] + dp[i + 1]
    cum[i + 1] %= mod
print(dp[N])
### BUGGY CODE ###

from collections import deque
s=deque(input())
q=int(input())
for i in range(q):
    t=list(map(str,input().split()))
    if int(t[0])==1:
        s.reverse()
        #print(s)
    else:
        if int(t[1])==1:
            s.appendleft(t[2])
        else:
            s.append(t[2])
for k in s:
    print(k,end='')                



### FIXED CODE ###

S=list(input())
#print(S)
q=int(input())
x=0
appends=[[] for i in range(2)]
for i in range(q):
    s=list(input().split())
    if int(s[0])==1:
        x+=1
    else:
        appends[(x+int(s[1])+1)%2].append(s[2])
        #print(appends)
if  x%2==1:
    S=S[::-1]
S=appends[x%2][::-1]+S+appends[(x+1)%2]
#print(S)
for k in S:
    print(k,end='')
### BUGGY CODE ###

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

res = 0
for i in range(n):
    for j in range(i+1, n):
        res += lst[i] * lst[j]
print(res % ((10**9)+7))


### FIXED CODE ###

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

ans = 0
summ = sum(lst)
summ_sq = summ**2
for i in range(n):
    ans += lst[i]**2

res = (summ_sq-ans)//2
print(res % ((10**9)+7))
### BUGGY CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, K, L = [int(_) for _ in input().split()]

C = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    C.unite(p, q)
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    C.unite(r + N, s + N)
ans = []
for i in range(1, N + 1):
    count = 0
    for j in range(1, N + 1):
        if C.same(i, j) and C.same(i + N, j + N):
            count += 1
    ans += [str(count)]
print(' '.join(ans))


### FIXED CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
s = 0
x = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        s += lst[i]^lst[j]
mod = 10 ** 9 + 7
print(s % mod)


### FIXED CODE ###

import sys
import numpy as np
 
n = int(input())
lst = [int(i) for i in sys.stdin.readline().split()]
arr = np.array(lst, np.int64)

mod = 10 ** 9 + 7
x_sum = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    x_sum += (c1 * (n - c1) * 2 ** i)
    x_sum %= mod
    arr >>= 1
print(x_sum)
### BUGGY CODE ###

N,K=map(int,input().split())
list=[]
for z in range(N):
    a,b=map(int,input().split())
    list.append([a,b])
numbers=[]
for y in range(N):
    numbers+=[list[y][0]]*list[y][1]
newnumbers=sorted(numbers)
print(newnumbers[K-1])


### FIXED CODE ###

N,K=map(int,input().split())
listA=[0]*10**5
for z in range(N):
    a,b=map(int,input().split())
    listA[a-1]+=b
count=0
y=0
while count<=10**5-1:
    y+=listA[count]
    if y>=K:
        print(count+1)
        break
    else:
        count+=1
### BUGGY CODE ###

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

ll = l % 2019
ans = 2018
if l-n >= 672:
    ans = 0
elif l-n > 2:
    for i in range(ll,ll + n-l +1):
        if i % 673 == 0:
            ans = 0
            break
        else:
            for j in range(ll,ll + n-l +1):
                if i != j:
                    ansss = i*j%2019
                    if ansss == 0:
                        ans = 0
                        break
                    elif ansss < ans:
                        ans = ansss
else:
    for i in range(ll,ll + n-l +1):
        for j in range(ll,ll + n-l +1):
            if i != j:
                ansss = i*j%2019
                if ansss == 0:
                    ans = 0
                    break
                elif ansss < ans:
                    ans = ansss

print(ans)

### FIXED CODE ###

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

ll = l % 2019
ans = 2018
if l-n >= 672:
    ans = 0
else:
    for i in range(ll,ll + n-l +1):
        if i % 673 == 0:
            ans = 0
            break
        else:
            for j in range(ll,ll + n-l +1):
                if i != j:
                    ansss = i*j%2019
                    if ansss == 0:
                        ans = 0
                        break
                    elif ansss < ans:
                        ans = ansss

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

import copy
N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1

A = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        A[i][i + j] = min(abs(x- i) +1 +abs(y-i-j),j)
A[X-1][Y-1] = 1
ans = []

for p in range(N):
    ans.append(sum(A, []))
for t in range(N):
    if t == 0:
        continue
    sum =  A.count(t)
    print(ans[0].count(t))




### FIXED CODE ###


N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1
ans = [0] * (N)
A = [[] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        path = min(abs(x- i) +1 +abs(y-i-j),j)
        ans[path] += 1
for _ in range(len(ans)):
    if _ == 0:
        continue
    print(ans[_])
### BUGGY CODE ###


MOD = 10**9+7
s = input()
sl = list(s)
n=len(s)
dsl={i:sl[i] for i in range(n)}

dp={i:[0]*13 for i in range(n+1)}

dp[0][0]=1
for i in range(n):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD

print(dp[n][5]%MOD)


### FIXED CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)
### BUGGY CODE ###

def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  step_lengthes = []
  for _ in range(K):
    L, R = map(int, input().split(" "))
    step_lengthes.extend(range(L, R+1))
  step_lengthes.sort()
  dp = [0] * (N+1)
  dp[1] = 1

  for i in range(1, N+1):
    for d in step_lengthes:
      if i+d <= N:
        dp[i+d] += dp[i]
      else:
        break
  print(dp[-1]%998244353)

if __name__ == "__main__":
  resolve()

### FIXED CODE ###

def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

  dp = [0] * (N+1)
  dp_sum = [0] * (N+1)
  dp[1] = 1
  dp_sum[1] = 1

  for i in range(2, N+1):
    for lr in LRs:
      left = max(i - lr[1] - 1, 0)
      right = max(i - lr[0], 0)
      dp[i] += dp_sum[right] - dp_sum[left]
      if dp[i] >= base:
        dp[i] %= base
      dp_sum[i] = dp_sum[i-1] + dp[i]
  print(dp[-1])

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

a = int(input())
x = list(map(int, input().split()))
k = list(x)
p = list(x)
for i in range(a):
    del k[i]
    #print(k)
    k.sort()
    #print(k)
    if a%2==0:
        print(k[a//2-1])
    else:
        print((k[a//2]+k[a//2-1])/2)
    k = list(p)
    

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = list(x)
y.sort()
if n % 2 != 0:
    a,b,c = y[n//2-1],y[n//2],y[n//2+1]
    m = b
else:
    a,b = y[n//2-1],y[n//2]    
    m = (a+b)/2
for i in range(n):
    if i == n//2:
        if n%2==0:
            tm = a
        else:
            tm = (a+c)/2
    if x[i] < m :
        if n%2==0:
            tm = b
        else:
            tm = (b+c)/2
    else:
        if n%2==0:
            tm = a
        else:
            tm = (a+b)/2
    print(int(tm))
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
table=[]
for i in range(n):
  table.append([int(i) for i in input().split()])
Chk=True
for k in range(n):
  for i in range(n):
    for j in range(n):
      if table[i][k]+table[k][j]<table[i][j]:
        Chk=False
        table[i][j]=table[i][k]+table[k][j]

ans=0
for i in range(n):
  for j in range(i+1,n):
    C=True
    for k in range(n):
      if k==i or k==j:
        continue
      else:
        if table[i][k]+table[k][j]==table[i][j]:
          C=False
    if C:
      ans+=table[i][j]
print(ans if Chk else -1)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
table=[]
for i in range(n):
  table.append([int(i) for i in input().split()])
Chk=True
for k in range(n):
  for i in range(n):
    for j in range(n):
      if table[i][k]+table[k][j]<table[i][j]:
        Chk=False
        table[i][j]=table[i][k]+table[k][j]

ans=0
for i in range(n):
  for j in range(i+1,n):
    C=True
    for k in range(n):
      if k==i or k==j:
        continue
      else:
        if table[i][k]+table[k][j]==table[i][j]:
          C=False
    if C:
      ans+=table[i][j]
print(ans if Chk else -1)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
L = [0] * len(set(A))
tmp = 0
for i in set(A):
    L[tmp] = A.count(i)
    tmp += 1
L.sort()
if len(set(A)) <= K:
    print('0')
else:
    print(str(sum(L[0:len(set(A))-K])))

### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = set(A)
    L = [0 for i in range(N+1)]
    for i in A:
        L[i] += 1
    L.sort()
    if len(B) <= K:
        print('0')
    else:
        print(str(sum(L[0:N+1-K])))


if __name__ == "__main__":
    main()