CF2237F Paint the Array

给定一个长度为 $n$ 的数组和一个固定整数 $m$。一次“涂色操作”定义如下： - 选择一个长度为 $m$ 的区间，并将其从左到右依次涂上数值 $1,2,\ldots,m$。形式上，选择一个整数 $l$，使得 $1\le l\le n-m+1$。然后对于每个 $1\le i\le m$，位置 $l+i-1$ 被涂上值 $i$。 如果一个位置被多次涂色，则只有最后一次涂色的数值会保留。 如果一个数组可以通过若干次涂色操作得到，并且每个位置至少被涂色一次，则称该数组为“合法”的。 给定一个数组 $a_1,a_2,\ldots,a_n$ （$1\le a_i\le m$），请你求出最少需要修改多少个元素（每次修改可以将某个数改为 $1$ 到 $m$ 之间的任意整数），才能使该数组合法。

每组测试包含多组测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1\le m\le n\le 5\cdot 10^5$），表示数组长度和每次涂色的区间长度。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le m$）。 保证所有测试用例中 $n$ 的总和不超过 $5\cdot 10^5$。

对于每个测试用例，输出一个整数，表示使该数组合法所需的最少修改次数。

以下转换中，下划线标出的为最近一次操作所涂的位置。 在第一个测试用例中，原数组已经合法。例如可以如下操作： $$ [-,-,-,-,-]\to[-,-,\underline{1},\underline{2},\underline{3}]\to[\underline{1},\underline{2},\underline{3},2,3]。 $$ 因此无需修改，答案为 $0$。 在第二个测试用例中，由于 $n=4$ 且 $m=3$，每个合法数组都必须通过“涂色”区间 $[1,3]$ 和 $[2,4]$ 得到。例如： $$ [-,-,-,-]\to[-,\underline{1},\underline{2},\underline{3}]\to[\underline{1},\underline{2},\underline{3},3]。 $$ 这样可以得到合法数组 $[1,2,3,3]$。给定的数组 $[1,2,2,3]$ 只需修改第三个元素即可变为合法数组，所以答案是 $1$。 在第三个测试用例中，最近的合法数组为 $[1,1,2,3,3]$，它的涂色过程如下： $$ [-,-,-,-,-]\to[\underline{1},\underline{2},\underline{3},-,-]\to[1,2,\underline{1},\underline{2},\underline{3}]\to[1,\underline{1},\underline{2},\underline{3},3]。 $$ 给定的数组 $[2,1,2,3,2]$ 与 $[1,1,2,3,3]$ 有两处不同。可以证明一次修改不足够使其变为合法数组，因此答案为 $2$。 由 ChatGPT 5 翻译