题目描述

给定一个包含 $n$ 个整数的数组，任务是计算每个大小为 $k$ 的滑动窗口的中位数，从左到右依次输出。

中位数是将元素排序后，位于中间的元素。如果元素个数为偶数，则有两个可能的中位数，我们取较小的那个。

输入格式

第一行输入两个整数 $n$ 和 $k$，分别代表数组的元素个数和滑动窗口的大小。

第二行输入 $n$ 个整数 $x_1, x_2, \ldots, x_n$，代表数组的值。

输出格式

输出 $n - k + 1$ 个整数，表示每个滑动窗口的中位数。

样例

8 3
2 4 3 5 8 1 2 1

3 4 5 5 2 1

数据范围

• $1 \le k \le n \le 2 \times 10^5$
• $1 \le x_i \le 10^9$