题目描述

有一个长度为 $n$ 的数组 $nums$ 和一个整数 $k$。

有一个大小为 $k$ 的滑动窗口从数组的最左端移动到最右端，每次移动一个位置。

对于每个滑动窗口，你需要输出其中元素的中位数。

中位数定义：

• 如果窗口大小为奇数，中位数是排序后位于中间的那个元素。
• 如果窗口大小为偶数，中位数是排序后中间两个元素的平均值。

输入格式

• 第一行包含两个整数 $n$ 和 $k$ $(1 \le k \le n \le 10^5)$，表示数组长度和窗口大小。
• 第二行包含 $n$ 个整数，表示数组 $nums$。每个数的绝对值不超过 $2^{31}-1$。

输出格式

输出一行，包含 $n-k+1$ 个小数，表示每个滑动窗口的中位数。

直接使用 cout 默认输出即可。

样例 #1

样例输入 #1

8 3
1 3 -1 -3 5 3 6 7

样例输出 #1

1 -1 -1 3 5 6

样例解释 #1

窗口位置                   中位数
[1  3  -1] -3  5  3  6  7      1
 1 [3  -1  -3] 5  3  6  7     -1
 1  3 [-1  -3  5] 3  6  7     -1
 1  3  -1 [-3  5  3] 6  7      3
 1  3  -1  -3 [5  3  6] 7      5
 1  3  -1  -3  5 [3  6  7]     6

样例 #2

样例输入 #2

5 2
1 2 3 4 5

样例输出 #2

1.5 2.5 3.5 4.5

样例解释 #2

窗口位置      中位数
[1 2] 3 4 5   1.5
1 [2 3] 4 5   2.5
1 2 [3 4] 5   3.5
1 2 3 [4 5]   4.5

样例 #3

样例输入 #3

5 1
10 20 30 40 50

样例输出 #3

10 20 30 40 50

提示

• 数组元素可能包含负数。
• $1 \le k \le n \le 10^5$。
• 需要高效的算法，$O(n^2)$ 的算法可能超时。