Median Range: Titan Online Assessment MNNIT Allahabad

Problem Preview

"You are given an array A of N integers. For every possible subarray, calculate its median. You need to determine the range of median values, i.e., the difference between the maximum possible median and the minimum possible median among all subarrays. Input Format The first line contains an integer N. The second line contains N integers A[i]. Output Format Print a single integer representing: maximum median - minimum median Constraints 1 ≤ N ≤ 2 × 10^5 1 ≤ A[i] ≤ 10^9 Example Input: 5 1 3 2 5 4 Output: 4 Explanation: The minimum possible median is 1, while the maximum possible median is 5. Therefore, the median range is 5 - 1 = 4."