CF2157E.Adjusting Drones

PIXL - This Time

你管理着一支由 $n$ 架无人机组成的机队，这些无人机的能量值分别为 $a_1, \ldots, a_n$。同时，给定一个正整数 $k$，表示最多允许多少架无人机拥有相同的能量值。

为了防止过载，无人机队会自动进行能量平衡操作。具体来说，只要存在某个特定的能量值在所有无人机中出现严格超过 $k$ 次，就会按照如下步骤进行能量平衡操作：

• 首先，如果一架无人机 $i$ 满足它的能量值 $a_i$ 在它之前已经出现过（即存在某个 $j < i$ 使得 $a_j = a_i$），则标记它；
• 然后，对每架被标记的无人机，将其能量值增加 $1$；
• 最后，清除所有标记。

如果仍然存在某个特定的能量值在所有无人机中出现严格超过 $k$ 次，上述过程就会再次执行，直到任何特定的能量值在所有无人机中出现都不超过 $k$ 次。

输入包含多组测试数据。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示有多少组测试数据。

对于每组测试数据：

第一行包含两个整数 $n, k$（$1 \le k \le n \le 2 \times 10^5$），分别表示无人机数量以及同一能量值在无人机队中允许出现的最大次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2n$），表示每一架无人机初始的能量值。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

对于每组测试数据，输出一行。

每行包含一个整数，表示这组测试数据需要执行的能量平衡操作的次数。

在第一组测试数据中，无人机队的能量值变化过程如下：

• 最初：$[1, 1, 1, 1, 1, 1]$；
• $1$ 次能量平衡操作后：$[1, 2, 2, 2, 2, 2]$；
• $2$ 次能量平衡操作后：$[1, 2, 3, 3, 3, 3]$；
• $3$ 次能量平衡操作后：$[1, 2, 3, 4, 4, 4]$；

在进行了 $3$ 次能量平衡操作后，每个能量值的出现次数都不超过 $3$，操作结束。

在第一组测试数据中，无人机队的能量值的变化过程如下：

$[1, 3, 2, 1, 4] \rightarrow [1, 3, 2, 2, 4] \rightarrow [1, 3, 2, 3, 4] \rightarrow [1, 3, 2, 4, 4] \rightarrow [1, 3, 2, 4, 5]$，因此总共进行了 $4$ 次能量平衡操作。