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 := ⌊(a_i)/(2)⌋).

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 ≤ k ≤ n ≤ 2 ⋅ 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, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 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
import java.util.*;
import java.io.*;

public class HelloWorld {
  public void run() throws Exception {
    Scanner file = new Scanner(System.in);
    int times = file.nextInt();
    int k = file.nextInt();
    ArrayList<Integer> w= new ArrayList();
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < times; i++) {
      int temp = file.nextInt();
      w.add(temp);
      max = Math.max(max, temp);
    }
    Collections.sort(w);
    int[] kamt = new int[200001], moves = new int[200001];
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < times; i++) {
      int temp = w.get(i);
      int count = 1;
      while (temp > 0) {
        kamt[temp]++;
        if (kamt[temp] >= k) min = Math.min(min, moves[temp]);
        temp /= 2;
        moves[temp] += count;
        count++;
      }
    }
    System.out.println(min);
  }

  public static void main(String[] args) throws Exception {
    new HelloWorld().run();
  }

}
