#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
 
double central_mean(const std::vector<int> &v, size_t i)
{
	return i & 1 ?  v.at(i) : 0.5 * (v.at(i - 1) + v.at(i));
};
 
 
int main() {
	std::vector<int> v1 {
		-1, 2, 1, 0, 7, 2, 3, 4, 0, 1, 5, 0, 2, 0, 0, 2
	};
	auto v2 {v1};
 
	std::sort(v1.begin(), v1.end());
	std::cout << "Sort:\n";
	std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));
	double median1 = central_mean(v1, v1.size() / 2);
 
	std::cout << "\nMedian: " << median1 << '\n';
 
	std::nth_element(v2.begin(), v2.begin() + v2.size()/2, v2.end());
	std::cout << "Nth_element:\n";
	std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, " "));
	double median2 = central_mean(v2, v2.size() / 2);
 
	std::cout << "\nMedian: " << median2 << '\n';
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aXRlcmF0b3I+CiNpbmNsdWRlIDx2ZWN0b3I+Cgpkb3VibGUgY2VudHJhbF9tZWFuKGNvbnN0IHN0ZDo6dmVjdG9yPGludD4gJnYsIHNpemVfdCBpKQp7CglyZXR1cm4gaSAmIDEgPyAgdi5hdChpKSA6IDAuNSAqICh2LmF0KGkgLSAxKSArIHYuYXQoaSkpOwp9OwoKCmludCBtYWluKCkgewoJc3RkOjp2ZWN0b3I8aW50PiB2MSB7CgkJLTEsIDIsIDEsIDAsIDcsIDIsIDMsIDQsIDAsIDEsIDUsIDAsIDIsIDAsIDAsIDIKCX07CglhdXRvIHYyIHt2MX07CgkKCXN0ZDo6c29ydCh2MS5iZWdpbigpLCB2MS5lbmQoKSk7CglzdGQ6OmNvdXQgPDwgIlNvcnQ6XG4iOwoJc3RkOjpjb3B5KHYxLmJlZ2luKCksIHYxLmVuZCgpLCBzdGQ6Om9zdHJlYW1faXRlcmF0b3I8aW50PihzdGQ6OmNvdXQsICIgIikpOwoJZG91YmxlIG1lZGlhbjEgPSBjZW50cmFsX21lYW4odjEsIHYxLnNpemUoKSAvIDIpOwoJCglzdGQ6OmNvdXQgPDwgIlxuTWVkaWFuOiAiIDw8IG1lZGlhbjEgPDwgJ1xuJzsKCQoJc3RkOjpudGhfZWxlbWVudCh2Mi5iZWdpbigpLCB2Mi5iZWdpbigpICsgdjIuc2l6ZSgpLzIsIHYyLmVuZCgpKTsKCXN0ZDo6Y291dCA8PCAiTnRoX2VsZW1lbnQ6XG4iOwoJc3RkOjpjb3B5KHYyLmJlZ2luKCksIHYyLmVuZCgpLCBzdGQ6Om9zdHJlYW1faXRlcmF0b3I8aW50PihzdGQ6OmNvdXQsICIgIikpOwoJZG91YmxlIG1lZGlhbjIgPSBjZW50cmFsX21lYW4odjIsIHYyLnNpemUoKSAvIDIpOwoJCglzdGQ6OmNvdXQgPDwgIlxuTWVkaWFuOiAiIDw8IG1lZGlhbjIgPDwgJ1xuJzsKCQoJcmV0dXJuIDA7Cn0=