class Finder {
public:
    int partition(vector<int>& arr, int left, int right) {
        int pivot = left;
        int lt = left + 1;
        int gt = right;
        while (true) {
            while (lt <= right && arr[lt] < arr[pivot]) lt++;
            while (gt >= left && arr[gt] > arr[pivot]) gt--;
            if (lt > gt) break;
            swap(arr[lt], arr[gt]);
            lt++;
            gt--;
        }
        swap(arr[pivot], arr[gt]);
        return gt;
    }
    
    int findKth(vector<int> arr, int n, int k) {
        // write code here
        k = n - k;
        int left = 0, right = arr.size() -1;
        int pivot = 0;
        do {
            pivot = partition(arr, left, right);
            if(pivot == k){
                break;
            }else if(pivot > k){
                right = pivot - 1;
            }else {
                left = pivot + 1;
            }
        }while(true);        

        return arr[pivot];
    }
};