Maximum and Minimum Median Subsequences

Given an integer array and a subsequence of length k, find the maximum and minimum medians among all subsequences. Input Description The first line contains two integers n and k, the length of the array and the length of subsequence. The second line contains an array of n integers. Output Description Print two integers, the maximum median and minimum median respectively. Sample Input 6 3 1 3 4 1 2 6 Sample Output 4 2 Constraints $1 \leq k \leq n \leq 10^5$ The numbers in the array range from $-10^9$ to $10^9$. Example Input 6 3 1 3 4 1 2 6