#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

// Find the median of a vector<int>

void PrintVector(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i)
        std::cout << nums[i] << " ";
    std::cout << std::endl;
}

int MedianUtil(vector<int>& nums, int left, int right, int k) {

    if (k > 0 && k <= (right - left + 1)) {

        int pivot = nums[right];
        int j = left - 1;
        for (int i = left; i <= right - 1; ++i) {
            if (nums[i] <= pivot) {
                ++j;
                swap(nums[i], nums[j]);
            }
        }
        ++j;
        swap(nums[j], nums[right]);

        if (j - left == k - 1)
            return nums[j + 1];
        if (j - left > k - 1)
            return MedianUtil(nums, left, j - 1, k);

        return MedianUtil(nums, j + 1, right, k - j + left - 1);
    }

    return numeric_limits<int>::min();
}

/*
int Median(vector<int>& nums) {
    return MedianUtil(nums, 0, nums.size() - 1, nums.size() / 2);
}
*/

int Median(vector<int>& nums) {
    nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end(), [](const int p1, const int p2){return (p1 < p2);});
    return(nums[nums.size() / 2]);
}

int main()
{
    vector<int> nums{3, 2, 1, 6, 6};

    PrintVector(nums);

    std::cout << Median(nums) << std::endl;

    return 0;
}