Suppose you are given a list of n integers S = [a1, a2, . . . , an], where n is odd. You are also given a non-negative integer k, which does not exceed n. k times, you may increase any entry of S by 1.

Design an O(n log n) or better algorithm that computes the maximum possible median of the final list. Note: for a list of length 2n + 1 the median is the value for which there are n elements larger, and n elements smaller.