Yet another MEX problem October Long Challenge

Yet another MEX problem Solution

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of [2,2,1] is 0, because 0 does not belong to the array.
• The MEX of [3,1,0,1] is 2, because 0 and 1 belong to the array, but 2 does not.
• The MEX of [0,3,1,2] is 4, because 0,1,2 and 3 belong to the array, but 4 does not.

You are given an array A of length N. You create a list B consisting of the MEX-es of all subarrays of the array A. Formally, for all pairs (l,r) such that 1≤l≤r≤N, you calculate MEX(Al,Al+1,…,Ar) and append the value in the list B. Find the K-th smallest value in the list B.

Note: Since the size of the input and output is large, please use fast input-output methods.

Input Format

• The first line contains T denoting the number of test cases. Then the test cases follow.
• The first line of each test case contains two space-separated integers N and K.
• The second line contains N space-separated integers A1,A2,…,AN denoting the given array.

Output Format

For each test case, output on a single line the K-th smallest value in the list B.

Constraints

• 1≤T≤3⋅10⁴
• 1≤N≤10⁵
• 1≤K≤N⋅(N+1)2
• 0≤Ai≤N
• Sum of N over all test cases does not exceed 2⋅10⁶.

Subtasks

Subtask 1 (10 points):

• 1≤N≤5⋅10³
• Sum of NN over all test cases does not exceed 5⋅10⁴.

Subtask 2 (90 points): Original constraints

Sample Input 1

3
3 4
1 0 2
3 2
2 1 3
3 6
0 1 2

Sample Output 1

1
0
3

Explanation

Test case 1: MEX(A1)=0, MEX(A1,A2)=2, MEX(A1,A2,A3)=3, MEX(A2)=1, MEX(A2,A3)=1, MEX(A3)=0. Hence the list B=[0,2,3,1,1,0] and the 4-th smallest value in B is 1.

Test case 2: The MEX of all subarrays of the array A is 0. Hence the 2-nd smallest element in the list B is 0.

October Long Challenge 2021

• Longest AND Subarray
• MEX-OR
• Digit Removal
• Yet another MEX problem
• Characteristic Polynomial Verification
• Chef at the Olympics
• Which Mixture
• Three Boxes