该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

数据分析

题目描述

小沙是一个热爱数据分析的学生。他最近收集了学校 $n$ 天的气温数据，想要分析每天的天气趋势。为了更好地理解数据，他决定每次取连续 $k$ 天的数据进行分析。

在每组k天的数据中，小沙特别关注其中气温排名第 $\frac{k}{3}$ 的日子（即第 $\frac{k}{3}$ 小的温度值）。他想知道，在每个长度为k的连续时间段中，排名第 $\frac{k}{3}$ 的温度值是多少。

现在给你 $n$ 天的温度数据，以及数字 $k$，请你帮他找出所有长度为k的子区间中第 $\frac{k}{3}$ 小的数字是多少（保证 $\frac{k}{3}$ 是整数）。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示总共有 $n$ 天的数据和滑动窗口的大小。 第二行包含 $n$ 个整数 $a_i$，表示这 $n$ 天的温度数据。

输出格式

输出包含 $n-k+1$ 行，每行一个整数，表示每个长度为 $k$ 的子区间中第 $\frac{k}{3}$ 小的数字。

样例

样例输入

7 3
1 3 2 4 5 6 7

样例输出

1
2
2
4
5

样例解释

• 第一个区间 $[1, 3, 2]$：排序后为 $[1, 2, 3]$，第 $\frac{k}{3} = 1$ 小的是 $1$
• 第二个区间 $[3, 2, 4]$：排序后为 $[2, 3, 4]$，第 $\frac{k}{3} = 1$ 小的是 $2$
• 第三个区间 $[2, 4, 5]$：排序后为 $[2, 4, 5]$，第 $\frac{k}{3} = 1$ 小的是 $2$
• 第四个区间 $[4, 5, 6]$：排序后为 $[4, 5, 6]$，第 $\frac{k}{3} = 1$ 小的是 $4$
• 第五个区间 $[5, 6, 7]$：排序后为 $[5, 6, 7]$，第 $\frac{k}{3} = 1$ 小的是 $5$

数据范围

对于 $25\%$ 的数据：$n \leq 100, k \leq 10$

对于 $50\%$ 的数据：$n \leq 1000, k \leq 100$

对于 $100\%$ 的数据：

• $3 \leq n \leq 2\times 10^5$

• $3 \leq k \leq n$

• $k \bmod 3 = 0$（保证 $\frac{k}{3}$ 是整数）

• $1 \leq a_i \leq 10^9$