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