『GROI-R2』 不空白的画布

我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。 但是现在画布已经不再空白，因为画布上已经有了当下的风景。我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1,k]$ 范围内的正整数表示。 坦尼尔还要画他已经翻了的茶杯。每一次作画，他可以选定画布上的任意一个位置，然后将这个位置上的颜色涂改成 $[1,k]$ 范围内的任意正整数。 最后，我们都知道这幅画是有记忆的。定义画上留下的记忆碎片数量为画上的**相同颜色连续块个数**。现在坦尼尔想知道，如果给定他作画的次数**上限**，那么画上的记忆碎片个数**最多**有多少。 **形式化题面** 你有连续的 $n$ 个方格，每个方格上有一个初始颜色 $c_i$，且保证 $1\le c_i \le k$。 你可以操作**至多** $m$ 次，每个操作为改变某个方格颜色，要求改变后的颜色范围仍在 $[1,k]$ 内。 我们称一个**极长相同颜色连续段**为一块，要求求出经过至多 $m$ 次操作后的**最多**块数。

本题有多组测试数据。 第一行输入一个正整数 $T$ 表示数据组数。 对于每组测试数据，第一行输入三个正整数 $n,m,k$，表示画布的长度，坦尼尔作画的次数上限和颜色的取值范围。 第二行输入一个长度为 $n$ 的整数序列 $c$，表示画布上每个位置的初始颜色。

对于每组测试数据，输出一行一个正整数，表示记忆碎片最多有多少个。

2
3 1 3
2 2 2
5 2 4
2 2 2 2 3

3
5

**样例解释** 对于第一组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，得到 $\{c_n\}=\{2,1,2\}$，块数为 $3$。 对于第二组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，将从左到右的第三个位置涂成颜色 $3$，得到 $\{c_n\}=\{2,1,3,2,3\}$，块数为 $5$。 **数据范围** **本题采用捆绑测试**。 | $\text{Subtask}$ | $\sum n\le$ | $m\le$ | $k\le$ | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $10$ | $3$ | $10$ | | $2$ | $5\times 10^5$ | $1$ | $5\times 10^5$ | $10$ | | $3$ | $10^3$ | $10^3$ | $10^3$ | $15$ | | $4$ | $5\times 10^5$ | $5\times 10^5$ | $3$ | $25$ | | $5$ | $5\times 10^5$ | $5\times 10^5$ | $5\times 10^5$ | $40$ | 对于 $100\%$ 的数据满足 $1\le n\le 5\times 10^5$，$1\le \sum n\le 5\times 10^5$，$1\le m\le n$，$3\le k \le 5\times 10^5$，$1\le c_i\le k$。