Subsequence Medians

Problem Statement

Subsequence Medians Problem An intern has n integers, the i -th of which is values[i] , and an integer k . A subsequence of length k is obtained by deleting some elements of values and keeping the order of the rest; it has k elements. Its median is the element at index floor((k - 1) / 2) of the subsequence after it is sorted in non-decreasing order - the lower of the two middle elements when k is even. Over all subsequences of length k , report the largest median and the smallest median. Complete the function medians , which receives values and k and returns [maximum median, minimum median] . Input Format The first line contains the integer n , the number of elements. The second line contains n space separated integers, the array values . The third line contains the integer k . Output Format Print two lines: the maximum median, then the minimum median. Constraints 1 <= n <= 10^5 0 <= values[i] <= 10^9 1 <= k <= n Examples Example 1 Input: 3 1 2 3 2 Output: 2 1 The sub