Equalizing by Division (hard version)

题意翻译

## 题目描述 简单版和困难版之间的唯一区别在于数组元素的数量。 给定一个数组$a$，包含$n$个整数。每次操作你可以选择任一$a_i$并且将其除$2$向下取整（也就是说，每次操作中你可以使$a_i:=\lfloor \frac{a_i}{2} \rfloor$）。 你可以对任何$a_i$进行任意次（可以是零次）操作。 你的任务是计算最小的操作次数使得至少$k$个数组中的数字相等。 别忘了在几次操作后可能会有$a_i=0$的情况出现，因此答案始终存在。 ## 输入格式 输入的第一行包含两个整数$n$和$k$（$1\le k\le n\le 2 \cdot 10^5$）——数组中的元素个数和需要相等的数字个数。 输入的第二行包含$n$个整数$a_i,a_2,\cdots , a_n$（$1\le a_i\le 2 \cdot 10^5$），其中$a_i$为$a$中的第$i$个元素。 ## 输出格式 输出一个整数——使得数组中有$k$个相等的数的最小操作次数。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

5 3
1 2 2 4 5

输出样例 #1

1

输入样例 #2

5 3
1 2 3 4 5

输出样例 #2

2

输入样例 #3

5 3
1 2 3 3 3

输出样例 #3

0