CF2085F2 Serval and Colorful Array (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $ n\le 4\cdot 10^5 $ . 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 4\cdot 10^5 $ ) — 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 $ 4\cdot 10^5 $ .

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