#include <iostream>
using namespace std;
int kth(int *arr, int l,int r,int k)
{
    long long x = arr[(l+r) / 2];
    int i=l,j=r;
    while(i<=j)
    {
        while(arr[i] < x) i++;
        while(arr[j] > x) j--;

        if(i<=j)
        {
            std::swap(arr[i],arr[j]);
            i++;
            j--;
        }
    }
    if(l<=k && k<=j)
        return kth(arr, l,j,k);
    if( i<=k && k<=r)
        return kth(arr, i,r,k);
    return arr[k];
}

int main() {
	int a[4] = {3, 6, 4, 5};
	cout << kth(a, 0, 4, 1) << endl;
	cout << kth(a, 0, 4, 2) << endl;
	cout << kth(a, 0, 4, 3) << endl;
	cout << kth(a, 0, 4, 4) << endl;
	return 0;
}