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 $ .

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 $ .

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 $ .