CF2237F.Paint the Array

Consider an array of length $n$, and a fixed integer $m$. A painting operation is defined as follows:

• Choose an interval of length $m$ and paint it with the values $1,2,\ldots,m$ from left to right.

  Formally, choose an integer $l$ such that $1\le l\le n-m+1$. Then, for every $1\le i\le m$, position $l+i-1$ is painted with value $i$.

If a position is painted multiple times, only the value painted most recently remains.

An array is called valid if it can be obtained by performing some painting operations such that every position is painted at least once.

Given an array $a_1,a_2,\ldots,a_n$ with $1\le a_i\le m$, find the minimum number of modifications needed to make it valid. One modification changes one element to any integer between $1$ and $m$.

考虑一个长度为 $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$，其中每个 $a_i$ 满足 $1\le a_i\le m$，求使其变为有效数组所需的最少修改次数。每次修改可将任意一个元素改为 $1$ 到 $m$ 之间的任意整数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le m\le n\le 5\cdot 10^5$) — the length of the array and the length of each painted interval.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le m$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the minimum number of modifications needed to make it valid.

对于每个测试用例，输出一个整数——使其变为有效所需的最少修改次数。

In the transformations below, the underlined positions are exactly the positions painted in the latest operation.

In the first test case, the array is already valid. It can be obtained by the following painting operations: $$ [-,-,-,-,-]\to[-,-,\underline{1},\underline{2},\underline{3}]\to[\underline{1},\underline{2},\underline{3},2,3]. $$ Therefore no modification is needed, and the answer is $0$.

In the second test case, since $n=4$ and $m=3$, every valid array must be obtained by painting both intervals $[1,3]$ and $[2,4]$. For example, $$ [-,-,-,-]\to[-,\underline{1},\underline{2},\underline{3}]\to[\underline{1},\underline{2},\underline{3},3]. $$ This gives the valid array $[1,2,3,3]$. The given array $[1,2,2,3]$ can be changed into it by modifying only the third element, so the answer is $1$.

In the third test case, one closest valid array is $[1,1,2,3,3]$, which can be obtained as follows: $$ [-,-,-,-,-]\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]. $$ The given array $[2,1,2,3,2]$ differs from $[1,1,2,3,3]$ in two positions. It can be proven that one modification is not enough, so the answer is $2$.

在以下变换中，带下划线的位置恰好是最近一次操作所涂色的位置。

在第一个测试用例中，数组已经是合法的。它可以通过以下涂色操作得到：

\[-,-,-,-,-\]\\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$。