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

def main():
    import sys

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N, Q = MI()
    c = [set([i]) for i in LI()]

    def seg_func(x, y):
        return x | y

    unit = set([])

    class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
        def __init__(self, N, seg_func, unit):
            self.N = N
            self.func = seg_func
            self.unit = unit
            self.tree = [self.unit] * (2 * self.N)

        def build(self, init_value):  # 初期値を[N,2N)に格納
            for i in range(self.N):
                self.tree[i + self.N] = init_value[i]
            for i in range(self.N - 1, 0, -1):
                self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

        def fold(self, L, R):  # [L,R)の区間取得
            L += self.N
            R += self.N
            vL = self.unit
            vR = self.unit
            while L < R:
                if L & 1:
                    vL = self.func(vL, self.tree[L])
                    L += 1
                if R & 1:
                    R -= 1
                    vR = self.func(self.tree[R], vR)
                L >>= 1
                R >>= 1
            return self.func(vL, vR)

    seg = SegTree(N, seg_func, unit)
    seg.build(c)

    for i in range(Q):
        l, r = MI()
        print(len(seg.fold(l - 1, r)))

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    import sys
    def MI():
        return map(int, sys.stdin.readline().rstrip().split())
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N,Q = MI()
    c = [0] + LI()
    lr = []
    for i in range(Q):
        l,r = MI()
        lr.append((i,l,r))

    from operator import itemgetter

    lr = sorted(lr,key=itemgetter(2))  # 右端rでソート
    a = 0
    d = {}  # d[i] = 玉iが現れた最も右の位置
    ANS = [0]*Q


    class BIT():
        def __init__(self, init_value):
            self.n = len(init_value)
            self.tree = [0] * (self.n + 1)
            for i in range(1, self.n + 1):
                x = init_value[i - 1]
                while i <= self.n:
                    self.tree[i] += x
                    i += i & (-i)

        def update(self, i, x):  # i(1-index)番目の値を+x
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
            return

        def query(self, i):  # 1番目からi(1-index)番目までの和を返す
            res = 0
            while i > 0:
                res += self.tree[i]
                i -= i & (-i)
            return res


    bit = BIT([0]*N)  # 最も右に現れた玉の位置を管理
    for i in range(1,N+1):
        if not c[i] in d.keys():
            d[c[i]] = i
            bit.update(i,1)
        else:
            bit.update(d[c[i]],-1)
            d[c[i]] = i
            bit.update(i, 1)
        while a <= Q-1 and lr[a][2] == i:
            j,l,r = lr[a]
            ANS[j] = bit.query(r)-bit.query(l-1)
            a += 1

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


if __name__ == '__main__':
    main()
### BUGGY 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)
 
    # divisors.sort()
    return divisors
 
n = int(input())
 
l = make_divisors(n)
ans = n-1
for i in range(0, len(l)):
  for j in range(0, len(l)):
    if l[i] * l[j] == n:
      ans = min(ans, (l[i]+l[j]-2))
 
print(ans)

### FIXED CODE ###

import math

n = int(input())
ans = n-1

for i in range(1, math.floor(math.sqrt(n))+1):
  if n % i == 0:
    ans = min(ans, (i+(n/i)-2))
      
print(int(ans))
### BUGGY CODE ###

I=lambda:map(int,input().split())
n,m=I()
r=range(n)
y=[[] for i in r]
z=[None for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i-1]+=[[j-1, k]]
  y[j-1]+=[[i-1,-k]]

for i in r:
  if z[i]==None:
    z[i]=0
    q=[i]
    while q:
      p=q.pop()
      for j,k in y[p]:
        if z[j]==None:
          q+=[j]
          z[j]=z[p]+k
        elif z[j]!=z[p]+k:
          print("No")
          exit()
print("Yes")


### FIXED CODE ###

I=lambda:map(int,input().split())
n,m=I()
r=range(n)
y=[[] for i in r]
z=[None for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i-1]+=[[j-1, k]]
  y[j-1]+=[[i-1,-k]]

for i in r:
  if z[i]==None:
    z[i]=0 
  q=[i]
  while q:
    p=q.pop()
    for j,k in y[p]:
      if z[j]==None:
        q+=[j]
        z[j]=z[p]+k
      elif z[j]!=z[p]+k:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

S = [s for s in input()]
Q = int(input())
front = []
end = []
cnt = 0
for _ in range(Q):
    T = input().split()
    if int(T[0]) == 1:
        cnt += 1
    else:
        F = int(T[1])
        C = [s for s in T[2]]
        if F == 1:
            if cnt%2==0:
                front = C+front
            else:
                end = end+C
        else:
            if cnt%2==0:
                end = end+C
            else:
                front=C+front
if cnt % 2 == 0:
    S = front+S+end
else:
    S.reverse()
    end.reverse()
    front.reverse()
    S = end+S+front

print(''.join(S))

### FIXED CODE ###

S = input()
Q = int(input())
front = ''
end = ''
cnt = 0
for _ in range(Q):
    T = input().split()
    if int(T[0]) == 1:
        cnt += 1
    else:
        F = int(T[1])
        C = T[2]
        if F == 1:
            if cnt%2==0:
                front = C+front
            else:
                end = end+C
        else:
            if cnt%2==0:
                end = end+C
            else:
                front=C+front
if cnt % 2 == 0:
    S = front+S+end
    print(S)
else:
    S = list(reversed(S))
    end = list(reversed(end))
    front = list(reversed(front))
    S = end+S+front
    print(''.join(S))
### BUGGY CODE ###

#入力値処理
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    one = 0
    for a in A:
        if (a >> i & 1) == 1:
            one += 1
    ans += one * (N - one) * 2 ** i
    ans %= mod
print(ans)


### FIXED CODE ###

#入力値処理
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    one = 0
    for a in A:
        if (a >> i & 1) == 1:
            one += 1
    ans += one * (N - one) * 2 ** i
    ans %= mod
print(ans)
### BUGGY CODE ###

import copy

def main(N, L):
    L.sort(reverse=True)

    triangles = 0

    for i, P in enumerate(L):
        Q_list = copy.copy(L)
        del Q_list[:i + 1]
        for j, Q in enumerate(Q_list):
            minR = P - Q + 1
            R_list = copy.copy(Q_list)
            del R_list[:j + 1]
            for R in R_list:
                if R >= minR:
                    triangles += 1
                else:
                    break

    print(triangles)

if __name__ == '__main__':
    N = int(input())
    L = list(map(int, input().split()))
    main(N, L)


### FIXED CODE ###

import copy
import bisect

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

triangles = 0

for i in range(N - 2):
    P = L[i]
    for j in range(i + 1, N - 1):
        Q = L[j]
        if P + Q <= L[j + 1]:
            continue
        maxR = P + Q - 1
        triangles += bisect.bisect_right(L, maxR) - (j + 1)

print(triangles)
### BUGGY CODE ###

from sys import stdin
S = input()
N = int(input())
Q =  [list(map(str, stdin.readline().split())) for _ in range(N)]
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
             S = "".join([S,Q[i][2]])#先頭
        else :
            S1 = "".join([Q[i][2],S])
            S = S1

if flag == True:
    print(S)
else:
    print(S[::-1])  

### FIXED CODE ###

from sys import stdin
S = input()
x = S
y =str()   
N = int(input())
Q =  [list(map(str, stdin.readline().split())) for _ in range(N)]
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
            x += Q[i][2]#先頭
        else :
            y += Q[i][2]
M = "".join([y[::-1],x])
if flag == True:
    print(M)
else:
    print(M[::-1])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
k = max(a)
for i in range(n):
    if a[i] < k:
        print(k)
    else:
        tmp = a[i]
        a[i] = 0
        print(max(a))
        a[i] = tmp


### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
bl = [0 for i in range(n)]
bl[0] = a[0]
br = [0 for i in range(n)]
br[0] = a[n - 1]
for i in range(1, n):
    bl[i] = max(bl[i - 1],a[i])
a.reverse()
for i in range(1, n):
    br[i] = max(br[i - 1],a[i])
br.reverse()
print(br[1])
for i in range(1, n - 1):
    print(max(bl[i - 1],br[i + 1]))
print(bl[n - 2])
### BUGGY CODE ###

def main():
    
    n,m = map(int,input().split())
    l = list(input())
    l = l[::-1]
    count = [-1]*(n+1)
    count[0] = 0
    check = 1
    i = 0

    while i < n+1:
        if count[i] != -1:
            a = -1
            for j in range(1,m+1):
                if i+j < n+1 and l[i+j] != "1":
                    count[i+j] = check
                    a = i+j
            
            check += 1
            if a == -1:
                print(-1)
                exit()
            else:
                i = a
            
            if count[-1] != -1:
                break
    count = count[::-1]

    ans = []
    a = 0
    for i in range(check-2,-1,-1):
        b = count.index(i)
        ans.append(b-a)
        a = b
    print(*ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    
    n,m = map(int,input().split())
    l = list(input())[::-1]
    ans = []
    i = 0
    l[0] = 0

    while i < n+1:
        if l[i] == 0:
            a = -1
            for j in range(m,0,-1):
                if i+j < n+1 and l[i+j] != "1":
                    a = i+j
                    ans.append(j)
                    l[a] = 0
                    break
            if a == -1:
                print(-1)
                exit()
            else:
                i = a
            
            if l[-1] == 0:
                break
    
    print(*ans[::-1])

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

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

A = []
B = []
for i in range(M):
  a, b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

flag = False
if 1 not in A:
  print ("IMPOSSIBLE")
else:
  for i in range(M):
    if A[i] == 1:
      for j in range(M):
        if A[j] == B[i] and B[j] == N:
          print ("POSSIBLE")
          flag =True
  if not flag:
    print ("IMPOSSIBLE")

### FIXED CODE ###

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

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

D1 = set(A[i][1] for i in range(M) if A[i][0] == 1)
D2 = set(A[i][0] for i in range(M) if A[i][1] == N)

if len(D1 & D2) != 0:
  print ("POSSIBLE")
else:
  print ("IMPOSSIBLE")
### BUGGY CODE ###

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

dp = [1000000000] * (N+K+2)
HHH.extend([0]*(K+2))

dp[0] = 0
"配るdpでやる？"

for i in range(0, N):
    for j in range(1, K+1):  # 1段~K段飛ぶ
        dp[i+j] = min(dp[i+j], dp[i]+abs(HHH[i+j]-HHH[i]))

print(dp[N-1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]


def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

n=int(input())
ss=list(map(int,input().split()))
s=sorted(ss)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[i]+s[j]>s[k]:
                ans+=1

print(ans)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = [int(_) for _ in input().split()]
l.sort()
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        cnt += max(0, bisect_left(l, l[i] + l[j]) - (j+1))
print(cnt)
### BUGGY CODE ###

from collections import Counter
import collections

N = int(input())
a = [input() for i in range(N)]

c = collections.Counter(a)

i = 0
list = []
if(len(c.most_common()) == 1):
	list.append(c.most_common()[0][0])
elif(len(c.most_common()) == N):
  list = a
else:
  ##for i in range(0,len(c.most_common())-1):
    while(c.most_common()[i][1] == c.most_common()[0][1]):
        list.append(c.most_common()[i][0])
        i += 1



list.sort()

print(' \n'.join(map(str, list)))

    



### FIXED CODE ###

from collections import Counter
import collections

N = int(input())
a = [input() for i in range(N)]

c = collections.Counter(a)
hoge = c.most_common()
i = 0

list = []
if(len(hoge) == 1):
	list.append(hoge[0][0])
elif(len(hoge) == N):
  list = a
else:
  ##for i in range(0,len(c.most_common())-1):
    while(hoge[i][1] == hoge[0][1]):
        list.append(hoge[i][0])
        i += 1



list.sort()

print(' \n'.join(map(str, list)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    # input
    N,W = map(int,input().split())
    w,v = [0 for _ in range(N)],[0 for _ in range(N)]
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    
    # init dp
    v_max = sum(v)
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]==float("inf"):
            pass
        elif dp[-1][i]<=W:
            ans = i
        else:

            pass
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    # input
    N,W = map(int,input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    
    # init dp
    v_max = sum(v)
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]<=W:
            ans = i
        else:
            pass
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map(int,input().split())
A = [int(a) for a in input().split()]

n = 1
c = 0

for i in range(N):
    if i <= K-1:
        n *= A[i]

    else:
        tmp = n
        tmp /= A[c]
        tmp *= A[i]

        if tmp > n:
            print("Yes")
        else:
            print("No")

        c += 1



### FIXED CODE ###

N,K = map(int,input().split())
A = [int(a) for a in input().split()]

n = 0

for i in range(K,N):
    if A[i] > A[n] :
        print("Yes")
    else:
        print("No")
    n+=1
### BUGGY CODE ###

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

ans=0
for i in range(n+1):
    ans=max(ans,((a*i)//b-(a*(i//b))))
print(ans)


### FIXED CODE ###

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

ans=0
t=min(b,n)
for i in range(t,max(t-3,-1),-1):
    ans=max(ans,((a*i)//b-(a*(i//b))))
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
hhh = list(map(int, input().split()))
h = np.array(hhh)
ans = 0

h_s_i = list(reversed(list(np.argsort(h))))
for i in range(len(h_s_i) - 1):
    if hhh[i] - 2 >= min(hhh[i+1:]):
        ans = 1

if ans == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
h = [0] + list(map(int, input().split()))

for i in range(n):
    if h[i] < h[i+1]:
        h[i+1] -= 1
    elif h[i] > h[i+1]:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        hoge = []
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge.append(next)
                    d[i][next] = d[i][q]+c
        queue = hoge
def func(x,l):
    if l == []:
        return 0
    ans = []
    for i in range(len(l)):
        ans.append(func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return min(ans)
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
hoge = [0]*(M)
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    d[i][next] = d[i][q]+c
                    if not(next in hoge[:l]):
                        hoge[l] = next
                        l += 1
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)
### BUGGY CODE ###

import numpy as np

n, max_weight = map(int, input().split())
WV = np.array([input().split() for _ in range(n)], np.int64)

W, V = zip(*WV)
dp = np.zeros((n, max_weight + 1), np.int64)

for i in range(n):
    for w in range(1, max_weight + 1):
        if w >= W[i]:
            dp[i, w] = max(dp[i - 1, w], dp[i - 1, w - W[i]] + V[i])
        else:
            dp[i, w] = dp[i - 1, w]

print(dp[n - 1, max_weight])


### FIXED CODE ###

n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
dp = list([0] * (max_weight + 1) for _ in range(n + 1))
for i in range(n):
    for w in range(1, max_weight + 1):
        if w >= W[i]:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - W[i]] + V[i])
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[n][max_weight])
### BUGGY CODE ###

N = int(input())
S = input()
CNT = 0
for i in range(N):
    for j in range(i,N):
        if S[j] != S[i]:
            for k in range(j,N):
                if S[k] != S[i] and S[k] != S[j] and j-i != k-j:
                    CNT += 1
print(CNT)

### FIXED CODE ###

N = int(input())
S = input()
CNTR = 0
CNTG = 0
CNTB = 0
for i in range(N):
    if S[i] == 'R':
        CNTR += 1
    if S[i] == 'G':
        CNTG += 1
    if S[i] == 'B':
        CNTB += 1
CONB = CNTR * CNTG * CNTB
CNT = 0
for i in range(N):
    for j in range(i,N):
        if S[j] != S[i]:
            k = j + (j-i)
            if k > N-1:
                continue
            if S[k] != S[i] and S[k] != S[j]:
                CNT += 1
print(CONB - CNT)
### BUGGY CODE ###

import numpy as np
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
d=np.array(d)
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)



### FIXED CODE ###

#import numpy as np
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#d=np.array(d,np.int64)
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)
### BUGGY CODE ###

import math
N=int(input())
a=input().split()
A=[int(b) for b in a]
numbers=[0]*(2*10**5)
for a in range(1,2*10**5+1):
    kosuu=A.count(a)
    if kosuu<=1:
        pass
    else:
        numbers.insert(a-1,kosuu)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
answers=[0]*(2*10**5)
for a in range(1,2*10**5+1):
    if numbers[a-1]>=2:
        b=combinations_count(numbers[a-1],2)
        answers[a-1]+=b
kotae=sum(answers)
for a in range(N):
    z=A[a]
    if answers[z-1]==0:
        print(0)
    else:
        answer=kotae-numbers[z-1]+1
        print(answer)
        

### FIXED CODE ###

import math
import sys
from collections import Counter
N=int(input())
a=sys.stdin.readline().split()
A=[int(b) for b in a]
numbers=[0]*N
count=Counter(A)
kotae=0
for a in range(N+1):
    b=count[a]
    kotae+=b*(b-1)//2
for a in A:
    print(kotae+1-count[a])
### BUGGY CODE ###

N, A, B = map(int, input().split())
h = []
for i in range(N):
    h.append(int(input()))
    
count = 0
while True:
    max_h = 0
    for i in range(N):
        if h[i] > max_h:
            max_h = h[i]
            max_num = i
    
    if max_h <= 0:
        break
    
    h = [x - B for x in h]
    h[max_num] += B - A
    count += 1

print(count)

### FIXED CODE ###

N, A, B = map(int, input().split())
h = []
for i in range(N):
    h.append(int(input()))
    
left = 0
right = max(h)

def can_kill(count):
    ness = 0
    for hp in h:
        ness += max(-(-(hp - B * count) // (A - B)), 0)
    if ness <= count:
        return True
    return False
    
while right - left > 1:
    middle = left + (right - left) // 2
    if can_kill(middle):
        right = middle
    else:
        left = middle

print(right)
### BUGGY CODE ###

n,m=map(int,input().split())
t=[]
s=list(map(int,input().split()))
def f(s):
    for i in list(set(s)):
        t.append(s.count(i))
    return sum(sorted(t)[:len(t)-m])   
print(f(s))  

### FIXED CODE ###

N,K=map(int,input().split())
d,ans={},0
for i in list(map(int,input().split())):
    d[i]=d.get(i,0)+1
s=sorted(d.values())
for i in range(len(s)-K):
    ans+=s[i]
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
a=[int(input()) for i in range(m)]
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(1e9+7)
    if i in a:
        dp[i]=0
print(int(dp[n]))

### FIXED CODE ###

n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
mod=10**9+7
broken=[False for _ in range(n+1)]
for _ in range(m):
    broken[int(input())]=True
    
for i in range(1,n+1):
    if broken[i]:
        continue
    dp[i]=(dp[i-1]+dp[i-2])%mod

print(dp[n])