CF2085F1 Serval and Colorful Array (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, $ n\le 3000 $ . You can hack only if you solved all versions of this problem. Serval has a magic number $ k $ ( $ k\ge 2 $ ). We call an array $ r $ colorful if and only if: - The length of $ r $ is $ k $ , and - Each integer between $ 1 $ and $ k $ appears exactly once in $ r $ . You are given an array $ a $ consisting of $ n $ integers between $ 1 $ and $ k $ . It is guaranteed that each integer between $ 1 $ and $ k $ appears in $ a $ at least once. You can perform the following operation on $ a $ : - Choose an index $ i $ ( $ 1\le i < n $ ), then swap $ a_i $ and $ a_{i+1} $ . Find the minimum number of operations needed to make at least one subarray $ ^{\text{∗}} $ of $ a $ colorful. It can be shown that this is always possible under the constraints of the problem. $ ^{\text{∗}} $ An array $ b $ is a subarray of an array $ a $ if $ b $ can be obtained from $ a $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 2\leq k\leq n\leq 3000 $ ) — the length of the array $ a $ and Serval's magic number. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1\leq a_i\leq k $ ) — the elements of the array $ a $ . It is guaranteed that each integer between $ 1 $ and $ k $ appears in $ a $ at least once. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3000 $ .

For each test case, output a single integer — the minimum number of operations needed to make at least one subarray of $ a $ colorful.

In the first test case, since the subarrays $ [a_1, a_2] = [1, 2] $ and $ [a_2, a_3] = [2, 1] $ are already colorful, we do not need to perform any operations. Thus, the answer is $ 0 $ . In the second test case, we can swap $ a_1 $ and $ a_2 $ to obtain $ [1, \underline{2, 1, 3}, 1, 1, 2] $ , which has a colorful subarray $ [a_2, a_3, a_4] = [2, 1, 3] $ . And the given array initially does not have any colorful subarrays, so the answer is $ 1 $ .