CodeChef October Chellange 2017 : Max Mex

PROBLEM:  You are given a multi-set S of N integers, and an integer K. You want to find the maximum value of minimal excluded non-negative integer (MEX) of the multi-set given that you are allowed to add at most any K integers to the multi-set. Find the maximum value of MEX that you can obtain.
Few examples of finding MEX of a multi-set are as follows. MEX of multi-set {0} is 1, {1} is 0, {0, 1, 3} is 2, {0, 1, 2, 3, 5, 6} is 4.

Input

The first line of the input contains an integer T denoting the number of testcases.
The first line of each test case contains two space seperated integers N and K denoting the size of the multi-set and the maximum number of extra integers that you can add in the multi-set respectively.
The second line contains N space separated integers denoting the multi-set S: S₁, S₂ ,.... S_N.

Output

For each testcase, output the answer in a single line.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10⁵
• 0 ≤ K ≤ 10⁵
• 0 ≤ S_i ≤ 2 * 10⁵

Subtasks

• Subtask #1 (15 points): K=0.
• Subtask #2 (85 points): Original Constraints.

Example

Input:
4
3 0
1 0 2
3 1
1 0 2
4 3
2 5 4 9
2 0
3 4

Output:
3
4
6
0

Explanation

Example case 1. As K = 0, so we can't add any element to the multi-set. Elements of the set are {1, 0, 2}. The MEX value of this set is 3.
Example case 2. As K = 1, you are allowed to add at most 1 element to the multi-set. The multi-set are {1, 0, 2}. You can add element 3 to the multi-set, and it becomes {1, 0, 2, 3}. The MEX value of this multi-set is 4. There is no other way to have higher value of MEX of the set by adding at most one element to the multi-set.



SOLUTION :   IN JAVA  

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Iterator;
import java.util.Collections;
import java.util.ArrayList;

 class MaxMex {
  
public static void main(String []args){
try{

    ArrayList<Integer> al=new ArrayList<Integer>();
    InputStreamReader isr=new InputStreamReader(System.in);
    BufferedReader br=new BufferedReader(isr,10);
    String []line0=br.readLine().split(" ");
    int t=Integer.parseInt(line0[0]);
  
    for(int i=0;i<t;i++){
      
        BufferedReader br1=new BufferedReader(isr,100000);
        String []line1=br1.readLine().split(" ");
        int n=Integer.parseInt(line1[0]);
        int ad=Integer.parseInt(line1[1]);
        //ar1=new int[ad];
         ArrayList<Integer> ar=new ArrayList<Integer>();
         BufferedReader br2=new BufferedReader(isr,2*100000);
            String []line2=br2.readLine().split(" ");
        for(int j=0;j<n;j++){
          
            ar.add(Integer.parseInt(line2[j]));
        }
        //int max=0;
        // Iterator itr=ar.iterator();
         // while(itr.hasNext()){
            //  if(max<(int)itr.next()){
                // max=(int)itr.next();
             // }
          //}
        //  System.out.println(max);
    int max=Collections.max(ar);
        for(int j=1;j<=ad+1;){
          
        for(int k=0;k<=max+ad+1;k++){
            int count=0;
            Iterator itr1=ar.iterator();
            while(itr1.hasNext()){
            if(k==(int)itr1.next()){
                count+=1;
            }
            }
            if(count==0){
              
                if(j<ad+1){
                ar.add(k);}
                if(j==ad+1){
                    al.add(k);
                }
                j++;
            }
        }
    }
      
  
    }
    Iterator i=al.iterator();
    while(i.hasNext())
    System.out.println(i.next());
}
catch(IOException e){
  
}
    }

}