Suppose you are given a list of n integers S = [a₁, a₂, . . . , a_n], 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. (in pseudo code please!!)

Note: for a list of length 2n + 1 the median is the value for which there are n elements larger, and n elements smaller