P1037重彩书遗年（paint）

【题目背景】

能源核心重新亮起后，遗迹最深处的记录壁也随之苏醒。壁面上的大部分纹彩已经损坏，只剩一套能够反复覆盖连续区域的书写装置，Ehundategh 希望借此恢复遗迹留下的往年记录。

【题目描述】

记录壁由依次排列的 $n$ 个纹位组成。能源核心启动后，每个纹位都显露出一个 $1\sim m$ 之间的整数，当前留在壁面上的内容形成序列 $a_1,a_2,\ldots,a_n$。

Ehundategh 在记录壁旁找到了仍能运转的书写装置。装置无法单独控制某个纹位，每次只能进行一次覆写。进行一次覆写时，需要选择一个长度恰好为 $m$ 的连续区间，并从左到右依次在其中写入 $1,2,\ldots,m$。

形式化地说，选择一个满足 $1\leq l\leq n-m+1$ 的整数 $l$。随后对于每个 $1\leq i\leq m$，将第 $l+i-1$ 个纹位写为 $i$。

书写装置可以反复启动，选择的区间也可以相互重叠。如果一个纹位被多次覆写，较早留下的纹彩会被新的纹彩遮住，壁面上只保留最后一次写入的整数。因此，即使选择了完全相同的一组区间，不同的覆写顺序也可能留下不同的记录。

遗迹原本会用这套装置保存每一年的重要事件。若一个长度为 $n$ 的序列能够通过若干次覆写得到，并且每个纹位都至少被覆写过一次，则称它是一份完整记录。执行覆写的次数和顺序均可以任意选择，但最终不能留下从未被书写装置触及的空白纹位。

漫长的沉没已经破坏了部分纹彩，当前序列不一定是一份完整记录。为了辨认记录壁原本书写的内容，Ehundategh 可以修复若干个纹位。每次修复需要选择一个纹位，并将其中的整数改为任意一个 $1\sim m$ 之间的整数。

Ehundategh 希望尽可能保留壁面上仍然可信的纹彩。请你求出至少需要修改多少个纹位，才能使当前序列成为一份完整记录。

当所需的最少修改次数被确定后，Ehundategh 也找到了对应的修复方式。最后一段完整记录没有说明遗迹由谁建造，也没有解释金白鱼为何引路，只让记录壁边缘重新显露出一条通往海面的安全道路。

众人抄录了仍能辨认的文字，完成了对遗迹内层的测绘，随后沿这条道路回到船队。晨光越过特西荼亚海时，沉没遗迹重新归于寂静，这次探索也终于告一段落。

【输入格式】

从文件 $\textbf{\textit{paint.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,m$，分别表示纹位数量与每次覆写的区间长度。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示当前记录。

【输出格式】

输出到文件 $\textbf{\textit{paint.out}}$ 中。

对于每组测试数据输出一行一个整数，表示使当前序列成为一份完整记录所需的最少修改次数。

【样例 1 输入】

10 425 331 2 3 2 344 351 2 2 365 372 1 2 3 285 392 2 2 2 2

【样例 1 输出】

10213243

【说明/提示】

【样例 1 解释】

第一组测试数据给出的序列已经是一份完整记录。可以先覆写区间 $[3,5]$，再覆写区间 $[1,3]$，最终得到序列 $1,2,3,2,3$。

第二组测试数据可以将第三个纹位修改为 $3$，得到完整记录 $1,2,3,3$，因此答案为 $1$。

【样例 2】

见选手目录下的 $\textbf{\textit{paint/paint2.in}}$ 和 $\textbf{\textit{paint/paint2.ans}}$。

该组样例符合测试点 $1\sim 6$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{paint/paint3.in}}$ 和 $\textbf{\textit{paint/paint3.ans}}$。

该组样例符合测试点 $7\sim 12$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{paint/paint4.in}}$ 和 $\textbf{\textit{paint/paint4.ans}}$。

该组样例符合测试点 $13\sim 19$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{paint/paint5.in}}$ 和 $\textbf{\textit{paint/paint5.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

设 $N$ 为单个测试点内所有测试数据的 $n$ 之和。

对于 $100\%$ 的数据，保证 $1\leq T\leq 10^4$，$1\leq m\leq n\leq 5\times 10^5$，$N\leq 5\times 10^5$，$1\leq a_i\leq m$。

特殊性质：保证所有测试数据均满足 $m\leq 2$。