CF2183B Yet Another MEX Problem

You are given an array $ a $ of length $ n $ , and an integer $ k $ . Let $ f(l,r) $ be the value of $ \operatorname{mex}(a_l,a_{l+1},\ldots,a_r) $ $ ^{\text{∗}} $ . You want to perform the following operation $ n-k+1 $ times: - Let the current length of the sequence be $ |a| $ . You need to find an interval $ [l, r] $ of length $ k $ such that $ \operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r). $ In other words, you need to select a window of size $ k $ such that among all windows of size $ k $ , the window you selected has the maximum $ \operatorname{mex} $ . If multiple $ [l,r] $ exist, you may select any. Then, you must select any integer $ i $ such that $ l \leq i \leq r $ , and delete $ a_i $ from $ a $ . That is, your new sequence will be $ [a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n] $ . For example, in the array $ [1,2,0,1,3,0] $ with $ k=3 $ , the two possible $ (l,r) $ pairs are $ (1,3) $ and $ (2,4) $ (since they each have $ \operatorname{mex} 3 $ , which is the maximum among all windows of size $ 3 $ ). Therefore, you can remove any one of the indices $ 1,2,3,4 $ in your next move. After $ n - k + 1 $ operations, you will have a sequence of length $ k-1 $ . Your objective is to maximize the $ \operatorname{mex} $ of the remaining elements. Please output the maximum $ \operatorname{mex} $ possible. $ ^{\text{∗}} $ The minimum excluded (MEX) of a collection of integers $ c_1, c_2, \ldots, c_k $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ c $ .

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 positive integers $ n $ and $ k $ ( $ 2 \le k \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 0 \le a_i \le n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

Output a single non-negative integer representing your answer.

In the first test case, we can select the interval $ [1,3] $ . Then, delete $ a_2 $ to obtain $ [0,0] $ . The process terminates, and the $ \operatorname{mex} $ of the remaining elements is $ 1 $ . In the third test case, we can perform the following operations: - Select $ i=1,j=3 $ . This is allowed because the $ \operatorname{mex} $ of all windows of size $ 3 $ is $ 3,0,3 $ , and the window $ [1,3] $ has a $ \operatorname{mex} $ of $ 3 $ , which is the largest. Then, remove $ a_2 $ . The sequence is now $ [0,2,1,0] $ . - Select $ i=2,j=4 $ . Then, remove $ a_2 $ . The sequence is now $ [0,1,0] $ . - Select $ i=1,j=3 $ . Then, remove $ a_1 $ . The sequence is now $ [1,0] $ . The process terminates, and the final $ \operatorname{mex} $ is $ 2 $ .