题目描述

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \ldots, a_n$，以及一个正整数 $m$。请你对序列中的每个位置 $i$（$1 \le i \le n$），计算在它前面的最多 $m$ 个元素中的最小值。

具体地，定义 $\mathrm{min\_val}(i)$ 为 $a_{\max(1,\,i-m+1)}$ 到 $a_{i-1}$ 这些元素中的最小值。特别地，当 $i = 1$ 时，前面没有元素，直接输出 $0$。

输入格式

第一行两个整数 $n$ 和 $m$，分别表示序列长度和窗口大小。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示给定的序列。

输出格式

输出 $n$ 行，每行一个整数。第 $i$ 行为 $\mathrm{min\_val}(i)$ 的值。

样例

6 2
7 8 1 4 3 2

0
7
7
1
1
3

提示

对于 $100\%$ 的数据，保证 $1 \le m \le n \le 2 \times 10^6$，$1 \le a_i \le 3 \times 10^7$。