#include <iostream>

#include <cmath>

#include <vector>

#include <ctime>

#include <time.h>

#include <stdlib.h>

using namespace std;

class Solution {

public:

    int selection(vector<int>& s, int k) {

    	// for rand()

    	srand((unsigned)time(0));

    	// [0,size-1]

		int v = s[rand() % (s.size())];

		vector<int> left, mid, right;

		// assign values to left, mid and right

		for (int i = 0; i < s.size(); i++) {

			if (s[i] < v)

			    left.push_back(s[i]);

			else if (s[i] == v)

			    mid.push_back(s[i]);

			else

			    right.push_back(s[i]);

		}

		// k < v

		if (k <= left.size())

		    return selection(left, k);

		else if (k > left.size() && k <= left.size()+mid.size())

		    return v;

		else

		// k > v

		    return selection(right, k-left.size()-mid.size());

	}

};

int main() {

	Solution s;

	int arr[11] = {2,36,5,21,8,13,11,20,5,4,1};

	vector<int> v(arr, arr+11);

	cout << s.selection(v,6) << endl;

	return 0;

}