CF2271E Array Emptying

You are given an array $ a $ of length $ n $ and an integer $ k $ . In one operation, choose any element $ x $ of the array. - If $ x \le k $ , erase $ x $ from the array. - Otherwise, erase $ x $ and insert two elements equal to $ \left\lceil \dfrac{x}{2} \right\rceil $ . In both cases, increase $ k $ by $ 1 $ after performing the operation. Find the minimum number of operations required to make the array empty.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 0 \le k \le n $ ) — the length of the array and the initial value of $ k $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer — the minimum number of operations required to make the array empty.

In the first example, initially $ k = 0 $ . We can perform the following operations: 1. Split an element equal to $ 4 $ into two elements equal to $ 2 $ ; $ k $ becomes $ 1 $ . 2. Erase an element equal to $ 1 $ ; $ k $ becomes $ 2 $ . 3. Erase an element equal to $ 2 $ ; $ k $ becomes $ 3 $ . 4. Erase an element equal to $ 2 $ ; $ k $ becomes $ 4 $ . 5. Erase an element equal to $ 4 $ ; $ k $ becomes $ 5 $ . 6. Erase an element equal to $ 4 $ ; $ k $ becomes $ 6 $ . The array becomes empty after $ 6 $ operations.In the fourth example, initially $ k = 2 $ . We can perform the following operations: 1. Split an element equal to $ 6 $ into two elements equal to $ 3 $ ; $ k $ becomes $ 3 $ . 2. Erase an element equal to $ 3 $ ; $ k $ becomes $ 4 $ . 3. Erase an element equal to $ 3 $ ; $ k $ becomes $ 5 $ . 4. Erase an element equal to $ 5 $ ; $ k $ becomes $ 6 $ . 5. Erase an element equal to $ 6 $ ; $ k $ becomes $ 7 $ . 6. Erase an element equal to $ 6 $ ; $ k $ becomes $ 8 $ . 7. Erase an element equal to $ 6 $ ; $ k $ becomes $ 9 $ . 8. Erase an element equal to $ 6 $ ; $ k $ becomes $ 10 $ . The array becomes empty after $ 8 $ operations.