CF1213D2 Equalizing by Division (hard version)

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.