You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1076 题。

题目描述

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

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

输入格式

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

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

输出格式

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

样例

8 3
2 4 3 5 8 1 2 1

3 4 5 5 2 1 

说明/提示

$1 \le k \leq n \le 2\cdot 10^5$；

$1 \leq x_i \le 10^9$。