#include <algorithm>
#include <iostream>
#include <stdexcept>
 
template<class C>
auto median(C const& c){
  using std::begin; using std::end;
  auto start = begin(c);
  auto finish = end(c);
  using iterator = decltype(start);
  std::vector<iterator> working;
  for(auto it = start; it != finish; ++it)
    working.push_back(it);
  if (working.empty())
      return start;
  std::nth_element(
      begin(working), begin(working) + working.size() / 2, end(working),
      [](iterator lhs, iterator rhs){
          return *lhs < *rhs;
      }
  );
  return *(begin(working) + working.size() / 2);
}
 
int main() {
    std::vector<int> v {4, 8, 15, 16, 23, 42};
 
    std::cout << *median(v) << std::endl;
}

I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkZXhjZXB0PgoKdGVtcGxhdGU8Y2xhc3MgQz4KYXV0byBtZWRpYW4oQyBjb25zdCYgYyl7CiAgdXNpbmcgc3RkOjpiZWdpbjsgdXNpbmcgc3RkOjplbmQ7CiAgYXV0byBzdGFydCA9IGJlZ2luKGMpOwogIGF1dG8gZmluaXNoID0gZW5kKGMpOwogIHVzaW5nIGl0ZXJhdG9yID0gZGVjbHR5cGUoc3RhcnQpOwogIHN0ZDo6dmVjdG9yPGl0ZXJhdG9yPiB3b3JraW5nOwogIGZvcihhdXRvIGl0ID0gc3RhcnQ7IGl0ICE9IGZpbmlzaDsgKytpdCkKICAgIHdvcmtpbmcucHVzaF9iYWNrKGl0KTsKICBpZiAod29ya2luZy5lbXB0eSgpKQogICAgICByZXR1cm4gc3RhcnQ7CiAgc3RkOjpudGhfZWxlbWVudCgKICAgICAgYmVnaW4od29ya2luZyksIGJlZ2luKHdvcmtpbmcpICsgd29ya2luZy5zaXplKCkgLyAyLCBlbmQod29ya2luZyksCiAgICAgIFtdKGl0ZXJhdG9yIGxocywgaXRlcmF0b3IgcmhzKXsKICAgICAgICAgIHJldHVybiAqbGhzIDwgKnJoczsKICAgICAgfQogICk7CiAgcmV0dXJuICooYmVnaW4od29ya2luZykgKyB3b3JraW5nLnNpemUoKSAvIDIpOwp9CgppbnQgbWFpbigpIHsKICAgIHN0ZDo6dmVjdG9yPGludD4gdiB7NCwgOCwgMTUsIDE2LCAyMywgNDJ9OwogICAgCiAgICBzdGQ6OmNvdXQgPDwgKm1lZGlhbih2KSA8PCBzdGQ6OmVuZGw7Cn0=