123456789
template <class RandIt, class T> T median(RandIt beg, RandIt end) { sort(beg, end); RandIt mid = beg + (end - beg) / 2; return (end - beg) % 2 == 0 ? (*mid + mid[-1]) / 2 : *mid; }
template <class RandIt> double median(RandIt beg, RandIt end) { sort(beg, end); RandIt mid = beg + (end - beg) / 2; return (end - beg) % 2 == 0 ? (*mid + mid[-1]) / 2 : *mid; }