Медиана скользящего окна

Дан список целых чисел nums и размер окна k, где 1 ≤ k ≤ длины списка. Окно из k подряд идущих элементов сдвигается по списку на одну позицию слева направо. Верните список медиан всех n − k + 1 окон по порядку.

Медиана окна — средний элемент после сортировки при нечётном k и среднее арифметическое двух средних элементов при чётном k; ответ — дробные числа. Значения лежат в пределах 32-битного целого, поэтому сумма двух может не поместиться в 32 бита. Ограничения: до 10 000 элементов; сортировать каждое окно заново слишком медленно.

Пример: [1, 3, -1, -3, 5, 3, 6, 7], 3 → [1.0, -1.0, -1.0, 3.0, 5.0, 6.0].

Источник: задача CodeShare