/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
			int arr[]={-1,0,3,5,9,12};
			int k=9;
			int res = kthSmallest(arr,k);	
			System.out.println(res);
	}
 
	 public static int kthSmallest(int[] nums,int k) {
 
        int n=nums.length;
        int low=0,high=n-1;
        k = k % n;
        while(low <= high){
        	int mid = low +(high - low) / 2;
        	if(mid == k-1){
        		return nums[mid];
        	}else if(mid < k-1){
        		low = mid + 1;
        	}else if(mid > k-1){
        		high = mid -1 ;
        	}
        }
        return Integer.MIN_VALUE;
    }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCQlpbnQgYXJyW109ey0xLDAsMyw1LDksMTJ9OwoJCQlpbnQgaz05OwoJCQlpbnQgcmVzID0ga3RoU21hbGxlc3QoYXJyLGspOwkKCQkJU3lzdGVtLm91dC5wcmludGxuKHJlcyk7Cgl9CgkKCSBwdWJsaWMgc3RhdGljIGludCBrdGhTbWFsbGVzdChpbnRbXSBudW1zLGludCBrKSB7CgogICAgICAgIGludCBuPW51bXMubGVuZ3RoOwogICAgICAgIGludCBsb3c9MCxoaWdoPW4tMTsKICAgICAgICBrID0gayAlIG47CiAgICAgICAgd2hpbGUobG93IDw9IGhpZ2gpewogICAgICAgIAlpbnQgbWlkID0gbG93ICsoaGlnaCAtIGxvdykgLyAyOwogICAgICAgIAlpZihtaWQgPT0gay0xKXsKICAgICAgICAJCXJldHVybiBudW1zW21pZF07CiAgICAgICAgCX1lbHNlIGlmKG1pZCA8IGstMSl7CiAgICAgICAgCQlsb3cgPSBtaWQgKyAxOwogICAgICAgIAl9ZWxzZSBpZihtaWQgPiBrLTEpewogICAgICAgIAkJaGlnaCA9IG1pZCAtMSA7CiAgICAgICAgCX0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIEludGVnZXIuTUlOX1ZBTFVFOwogICAgfQp9