Sliding Window Medians

You are given an integer array nums of length n and an integer k. For every contiguous window of k elements, from left to right, compute the window's median.

The median is the middle element of the window in sorted order. When k is even there are two middle elements; take the smaller of the two.

Return the medians as an array of n - k + 1 values.

Examples

Example 1

Input: nums = [2, 4, 3, 5, 8, 1, 2, 1], k = 3
Output: [3, 4, 5, 5, 2, 1]
Explanation: The first window [2, 4, 3] sorts to [2, 3, 4], median 3. The
next window [4, 3, 5] sorts to [3, 4, 5], median 4, and so on.

Example 2

Input: nums = [1, 9, 2, 8], k = 2
Output: [1, 2, 2]
Explanation: Each window has two elements; the smaller of the two middles is
taken, e.g. [1, 9] gives 1.