CF2242C Unstable Elements

给定一个已排序的整数数组 $[a_1, a_2, \cdots, a_n]$。我们可以对该数组执行任意次数的以下操作类型： - 标记数组的第一个元素，以及所有不等于其左侧相邻元素的元素（即所有满足 $a_i \neq a_{i - 1}$ 的元素 $i$）。 - 然后删除所有标记元素或复制它们（即，用两个相同的元素替换每个标记元素）。 例如，考虑数组 $[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$（标记元素以粗体显示）。若删除所有标记元素，则得到 $[1, 1, 4]$；若复制这些标记元素，则得到 $[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$。 若数组为空，则无法执行操作。每次操作后，所有元素均会被取消标记。 我们称一个整数数组 $b$ 为可达的，如果它可以通过若干次所述操作从数组 $a$ 获得。你的任务是统计长度为 $k$ 的可达数组的数量。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例由两行组成： - 第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 3 \cdot 10^5$）； - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（满足 $1 \le a_1 \le a_2 \le \dots \le a_n \le n$）。注意该数组已排序。 - 所有测试用例的 $n$ 值总和不超过 $3 \times 10^5$。

对于每个测试用例，输出一个整数，表示长度为 $k$ 的可访问数组 $b$ 的数量。可以证明，在问题的约束下，答案符合标准的 $32$ 位整数类型。

在第一个示例中, 可以执行以下操作序列：$[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$。 在第二个例子中, 不可能得到长度为 $5$ 的数组。 在第三个示例中, 可以执行以下操作序列：$[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$。 在第五个例子中，可以得到数组 $[1, 1, 2, 2, 2, 2]$ 和 $[2, 2, 2, 2, 2, 2]$： - $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$； - $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$。 在第七个示例中，可以得到数组 $[1, 1, 1, 3, 3, 3, 3]$ 和 $[3, 3, 3, 3, 3, 3, 3]$。