CF2098B Sasha and the Apartment Purchase

Sasha 想在一条街道上购买一套公寓，这条街道上的房屋从左到右编号为 $1$ 到 $10^9$。 这条街道上有 $n$ 家酒吧，分别位于编号为 $a_1, a_2, \ldots, a_n$ 的房屋中。注意，可能有多个酒吧位于同一房屋中，这种情况下这些酒吧被视为不同的酒吧。 Sasha 担心在他购买公寓时，部分酒吧可能会关闭，但最多不超过 $k$ 家酒吧会关闭。 对于任意编号为 $x$ 的房屋，定义 $f(x)$ 为所有开放酒吧 $y$（即关闭部分酒吧后）的 $|x - y|$ 之和。 Sasha 可以购买编号为 $x$（$1 \le x \le 10^9$）的房屋中的公寓，当且仅当可以通过关闭最多 $k$ 家酒吧，使得 $f(x)$ 在所有房屋中达到最小值。 请确定 Sasha 可以购买公寓的不同房屋数量。

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$，$0 \leq k < n$）——酒吧数量和最多可以关闭的酒吧数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）——酒吧所在的房屋编号。 保证所有测试用例的 $n$ 之和不超过 $10^5$。

对于每个测试用例，输出一个整数——Sasha 可以购买公寓的房屋数量。

在第一个测试用例中，没有酒吧可以关闭，因此只有编号为 $2$ 和 $3$ 的房屋是合适的。对于编号为 $2$ 的房屋，距离之和为 $|2 - 1| + |2 - 2| + |2 - 3| + |2 - 4| = 4$；对于编号为 $3$ 的房屋，距离之和为 $|3 - 1| + |3 - 2| + |3 - 3| + |3 - 4| = 4$。然而，对于编号为 $1$ 的房屋，距离之和为 $|1 - 1| + |1 - 2| + |1 - 3| + |1 - 4| = 6$，因此编号为 $1$ 的房屋不合适。可以证明 Sasha 也无法在其他房屋购买公寓。 在第二个测试用例中，合适的房屋编号为 $6$ 和 $7$。如果 Sasha 选择编号为 $6$ 的房屋，只需不关闭任何酒吧。如果 Sasha 选择编号为 $7$ 的房屋，可以关闭编号为 $1$ 和 $6$ 的房屋中的酒吧。此时开放的酒吧将位于编号为 $6$、$7$ 和 $7$ 的房屋中。 翻译由 DeepSeek V3 完成