考虑一个长度为 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 完成该测试所需的最小修改次数 有效.
示例
输入复制
155 31 2 3 2 34 31 2 2 35 32 1 2 3 25 32 2 2 2 25 41 1 3 4 16 31 1 1 2 1 18 51 2 1 2 3 4 5 15 32 3 1 1 28 41 2 3 2 3 2 3 44 44 3 2 15 11 1 1 1 17 33 3 3 2 1 1 110 31 2 3 1 2 2 3 1 2 37 31 3 2 3 2 1 210 41 4 3 3 2 3 4 4 2 2
输出复制
012322142404134
注意
在下面的转换中,下划线位置正是最近一次操作中绘制的位置。
在第一个测试用例中,数组已经是 有效。可以通过如下绘制操作得到:$$[-,-,-,-,-]\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$$$。