The only difference between easy and hard versions is the number of elements in the array.

You are given an array $a$ consisting of $n$ integers. In one move you can choose any $a_i$ and divide it by $2$ rounding down (in other words, in one move you can set $a_i := \lfloor\frac{a_i}{2}\rfloor$).

You can perform such an operation any (possibly, zero) number of times with any $a_i$.

Your task is to calculate the minimum possible number of operations required to obtain at least $k$ equal numbers in the array.

Don't forget that it is possible to have $a_i = 0$ after some operations, thus the answer always exists.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of elements in the array and the number of equal numbers required.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

Print one integer — the minimum possible number of operations required to obtain at least $k$ equal numbers in the array.


-----Examples-----
Input
5 3
1 2 2 4 5

Output
1

Input
5 3
1 2 3 4 5

Output
2

Input
5 3
1 2 3 3 3

Output
0

Difficulty: introductory

Starter code:

Solutions:
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
from collections import defaultdict
from collections import deque
import math
import copy
 
#T = int(input())
#N = int(input())
#s1 = input()
#s2 = input()
N,K = [int(x) for x in stdin.readline().split()]
arr = [int(x) for x in stdin.readline().split()]
arr.sort()

freq = {}

for i in range(N):
    num = arr[i]
    if num not in freq:
        freq[num] = []
        
    round = 0
    freq[num].append(0)
    while num!=0:
        round += 1
        num = num//2
        if num not in freq:
            freq[num] = []
            
        freq[num].append(round)

res = 999999999999
for key in freq:
    if len(freq[key])<K:
        continue
    else:
        s = sum(freq[key][:K])
        res = min(res,s)
        
print(res)
        


import math
from heapq import merge
n, k = list(map(int, input().split()))
maxN = 2 * (10 ** 5) + 10
cnt = [list() for i in range(0, maxN + 1)]
a = list(map(int, input().split()))
for c in a:
    cnt[c].append(0)
best = 1000000000
for i in range(maxN - 1, -1, -1):
    if 2 * i < maxN:
        cnt[2 * i] = [x + 1 for x in cnt[2 * i]]
        for p in cnt[2 * i]:
            p += 1
    if 2 * i + 1 < maxN:
        cnt[2 * i + 1] = [x + 1 for x in cnt[2 * i + 1]]
    if 2 * i < maxN:
        cnt[i] = list(merge(cnt[i], list(merge(cnt[2 * i], cnt[2 * i + 1]))))
    while len(cnt[i]) > k:
        cnt[i].pop()
    if len(cnt[i]) == k:
        best = min(best, sum(cnt[i]))
print(best)


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

cnt = dict()
sum = dict()

res = n * 20

for x in a:
    y = x
    cur = 0
    while True:
        if y == 0:
            break
        if y not in cnt:
            cnt[y] = 0
            sum[y] = 0
        if cnt[y] < k:
            cnt[y] += 1
            sum[y] += cur
            if cnt[y] == k:
                res = min(res, sum[y])
        y >>= 1
        cur += 1
print(res)

n,k=list(map(int,input().split()))
it=list(map(int,input().split()))
a=[[] for i in range(n)]
ss={}
for i in range(n):
    j=it[i]
    a[i]=[j]
    try:
        ss[j].append(0)
    except:
        ss[j]=[0]
    st=0
    while True:
        st+=1
        j=j//2
        try:
            ss[j].append(st)
        except:
            ss[j]=[st]
        a[i].append(j)
        if j==0:
            break
tt=ss.copy()
mi=10**10
for i in ss:
    if len(ss[i])>=k:
        tt[i].sort()
        mi=min(mi,sum(tt[i][:k]))
print(mi)

        
        
            


"""
useful stuff 
x= list(map(int,input().split()))
x =[int (e) for e in input().split()]

swap x,y=y,x
substring a[x:y] mean x to y-1

print list
print(*list)
print(' '.join(map(str,listname)))

start from 1 to n
for i in range(1,n+1)

Don't froget dumb stuff like:
if: 
for:
while: 
and tab
def doesn't require data type
"""
z= []
a = []
for i in range (200010):
    a.append([])
n,k = [int (e) for e in input().split()]
b = [int (e) for e in input().split()]
for x in b:
    c=x
    ct=0
    a[x].append(0)
    while(c!=0):
        c>>=1
        ct+=1
        a[c].append(ct)
ans=10000000000
for i in range(200000):
    if(len(a[i])<k):
        continue
    a[i].sort()
    s=0
    for j in range(k):
        s+=a[i][j]
    ans=min(ans,s)
print(ans)


n, k = [int(x) for x in input().split()]
nums = sorted([int(x) for x in input().split()])
count = [0 for _ in range(2 * 100000 + 10)]
ops = [0 for _ in range(2 * 100000 + 10)]
for num in nums:
    op = 0
    while (num > 0):
        ops[num] += op if count[num] < k else 0
        count[num] += 1
        num = num // 2
        op += 1
    ops[num] += op if count[num] < k else 0
    count[num] += 1

minn = 0
minop = ops[0]
for i in range(2 * 100000 + 1):
    if (count[i] >= k and ops[i] < minop):
        minn = i
        minop = ops[i]

print(minop)


n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[[0,0] for i in range(200001)]
a.sort()
for i in range(n):
    ans[a[i]][0]+=1
for i in range(n):
    s=a[i]
    d=1
    while (s>0):
        s=s//2
        if ans[s][0]<k:
            ans[s][0]+=1
            ans[s][1]+=d
        d+=1
mi=100000000
for i in range(len(ans)):
    if ans[i][0]>=k:
        if ans[i][1]<mi:
            mi=ans[i][1]
print(mi)

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

numbers = [[0, 0] for i in range(a[-1]+1)]

for i in range(n):
    op = 0
    
    while a[i] > 0:
        if numbers[a[i]][0] < k:
            numbers[a[i]][0] += 1
            numbers[a[i]][1] += op
        
        a[i] //= 2
        op += 1
        
    numbers[0][0] += 1
    numbers[0][1] += op
    
ans = numbers[0][1]

for number in numbers:
    if number[0] >= k and number[1] < ans: ans = number[1]
        
print(ans)

MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, m = I()
l = I()
l.sort()
ans = MOD
o = [0]*300000
d = [0]*300000
for i in range(n):
	k = l[i]
	o[k] += 1
	if o[k] == m:
			ans = min(ans, d[k])
	i = 0
	while k > 0:
		i += 1
		k //= 2
		o[k] += 1
		d[k] += i
		if o[k] == m:
			ans = min(ans, d[k])

print(ans)

from math import log


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

ans = 0
a = [[] for i in range(200001)]
for i in range(n):
    x = arr[i]
    l = 0
    while True:
        a[x].append(l)
        if x == 0:
            break
        x //= 2
        l += 1
mn = 1000000000
for i in range(len(a)):
    a[i].sort()
    if len(a[i]) >= k:
        mn = min(mn, sum(a[i][:k]))
print(mn)


import collections
n,k=list(map(int,input().split()))
A=[int(i) for i in input().split()]
ans=float("inf")
D1,D2=collections.defaultdict(list),collections.defaultdict(int)
for i in range(n):
  a=A[i]
  c=0
  D1[a].append(c)
  D2[a]+=1
  while a>0:
    a//=2
    c+=1
    D1[a].append(c)
    D2[a]+=1
for i in range(max(A)+1):
  if D2[i]>=k:
    D1[i].sort()
    ans=min(ans,sum(D1[i][:k]))
print(ans)



'''input
5 3
1 2 3 3 3
'''
from collections import defaultdict as dd

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

d = dd(list)
for x in a:
	i = 0
	while(x):
		d[x].append(i)
		x //= 2
		i += 1
ans = 999999999999
for i in d:
	if len(d[i]) >= k:
		d[i].sort()
		ans = min(ans, sum(d[i][0:k]))
print(ans)

from collections import defaultdict as DD
import sys
MOD=pow(10,9)+7

def IN(f=0):
    if f==0:
        return ( [int(i) for i in sys.stdin.readline().split()] )
    else:
        return ( int(sys.stdin.readline()) )

n,k=IN()
a=IN()
b=[]

d=DD(list)
for x in a:
    i=0
    while(x!=0):
        d[x].append(i)
        x=x//2
        i+=1
    d[0].append(i)
    #print(d)

ans=9999999999999
for x in d:
    if len(d[x])>=k:
        r=d[x]
        r.sort()
        ans=min(ans,sum(r[:k]))
print(ans)
        




n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
value_lists = [[] for _ in range(2 * (10**5) + 1)]
for val in arr:
    turn = 0
    while val != 1:
        value_lists[val].append(turn)
        val //= 2
        turn += 1
    value_lists[val].append(turn)
mindist = 999999999
for turns_val in value_lists:
    if len(turns_val) < k:
        continue
    turns_val.sort()
    mindist = min(mindist, sum(turns_val[:k]))
print(mindist)


n, k = map(int,input().split())
l = list(map(int,input().split()))
d = {}
for liczba in l:
    ll = liczba
    while ll > 0:
        d[ll] = []
        ll //= 2
for liczba in l:
    i = 0
    ll = liczba
    while ll > 0:
        d[ll].append(i)
        ll //= 2
        i += 1
wyn = 1000000000
for number in d:
    if len(d[number]) < k:
        continue
    a = d[number].copy()
    a.sort()
    wyn = min(wyn, sum(a[:k]))
print(wyn)

ans = {}
n,k = (int(s) for s in input().split())
l = [int(s) for s in input().split()]
l.sort()

for i in range(n):
    x = l[i]
    count = 0
    while (x>0):
        if x in ans:
            if ans[x][0] <k:
                ans[x][0]+=1
                ans[x][1]+=count
        else:
            ans[x] = [1, count]
        count+=1
        x = x//2
    if 0 in ans:
        if ans[0][0] < k:
            ans[0][0] += 1
            ans[0][1] += count
    else:
        ans[x] = [1, count]
# print(ans)
ansm = 1000000000007
for i in ans:
    if ans[i][0]>=k:
        ansm = min(ansm, ans[i][1])
print(ansm)


b = {}
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b[0] = []
for x in a:
    j = 0
    while(x > 0):
        if(x in b):
            b[x].append(j)
        else:
            b[x] = [j]
        x //= 2
        j += 1
    b[0].append(j)

ans = 10**10

for i in b:
    b[i].sort()
    if(len(b[i]) >= k):
        ans = min(sum(b[i][:k]), ans)

print(ans)


n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
G = []
for _ in range(2 * 10 ** 5 + 100):
    G.append([])
c = 0
for i in A:
    if len(G[i]) < k:
        G[i].append(0)
while True:
    c += 1
    f = True
    for i in range(n):
        if A[i]:
            A[i] //= 2
            if len(G[A[i]]) < k:
                G[A[i]].append(c)
        if A[i]:
            f = False
    if f:
        break
ans = 10 ** 9
for t in G:
    if len(t) == k:
        ans = min(ans, sum(t))
print(ans)


from sys import stdin

input = stdin.readline
inf = 1000 * 1000 * 1000

n, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]

b = []
for i in range(200001):
    b.append([])

for i in a:
    ctr = 0
    while i > 0:
        b[i].append(ctr)
        i //= 2
        ctr += 1
    b[i].append(ctr)

res = inf
for i in b:
    if len(i) >= k:
        i.sort()
        tmp = 0
        for j in range(k):
            tmp += i[j]
        res = min(res, tmp)


print(res)


def deep(mas, pref, k):
    deepmas = []
    s = 0
    for el in mas:
        if el[:len(pref)] == pref:
            deepmas.append(el)
            if len(deepmas) <= k:
                s += len(el) - len(pref)
    if len(deepmas) >= k:
        return min(s, deep(deepmas, pref + '0', k), deep(deepmas, pref + '1', k))
    else:
        return 20000000000000000

n, k = list(map(int, input().split()))
mas = list(map(int, input().split()))
mas.sort()
mas = list(map(bin, mas))
pref = '0b'
ans = deep(mas, pref, k)
print(ans)


from sys import stdin,stdout

def __starting_point():
    n,k=list(map(int,stdin.readline().split()))
    a=list(map(int,stdin.readline().split()))
    num=[[] for i in range(200005)]
    ans=200000*100
    for x in a:
        cnt=0
        while x>0:
            num[x].append(cnt)
            x//=2
            cnt+=1
        num[x].append(cnt)
    for i in range(200001):
        if len(num[i])<k:
            continue
        num[i].sort()
        cnt=0
        for j in range(k):
            cnt+=num[i][j]
        ans=min(ans,cnt)
    stdout.write('%d\n'%(ans))



__starting_point()

from collections import *
n,k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
d = defaultdict(lambda: [0,0])
for i in A:
	num = i
	stp = 0
	while num>0:
		if d[num][0]<k:
			d[num][0]+=1
			d[num][1]+=stp
		num = num//2
		stp +=1
	if d[num][0]<k:
			d[num][0]+=1
			d[num][1]+=stp

mn = 10**20
for i in d:
	if(d[i][0]>=k):
		mn = min(d[i][1],mn)

print(mn)

MAX = 2 * 10 ** 5


def main():
    n, k = list(map(int, input().split()))
    a = sorted(map(int, input().split()))

    ops = [0] * (MAX + 1)
    ks = [0] * (MAX + 1)

    for x in a:
        c = x
        j = 0

        while True:
            if ks[c] < k:
                ops[c] += j
                ks[c] += 1

            if c == 0:
                break

            c //= 2
            j += 1

    min_ops = float('inf')
    for i in range(MAX + 1):
        if ks[i] == k:
            min_ops = min(ops[i], min_ops)

    print(min_ops)


main()


def main():
    n,k = list(map(int,input().split()))
    arr = list(map(int,input().split()))
    nums = [[0 for i in range(2)] for j in range(2*10**5+1)]
    arr.sort()
    for i in arr:
        moves = 0
        #print('start')
        while i >= 0:
            if nums[i][0] == k:
                break
            nums[i][0] += 1
            nums[i][1] += moves
            moves += 1
            i = i//2
            if i == 0:
                nums[i][0] += 1
                nums[i][1] += moves
                break

    min_moves = float('inf')
    for i in range(2*10**5+1):
        if nums[i][0] >= k:
            min_moves = min(min_moves,nums[i][1])

    print(min_moves)


main()


n,k1=map(int,input().split())
li=list(map(int,input().split()))
d={}
for i in li:
    k=0
    while i!=0:
        try:
            d[i].append(k)
        except KeyError:
            d[i]=[k]
            
        k+=1
        i=i//2
mi=100000000
for i in d.values():
    if len(i)>=k1:
        i.sort()
        mi=min(mi,sum(i[:k1]))
print(mi)