Sliding Window - Sliding Minimum Elements

Time Limit : 2 sec, Memory Limit : 262144 KB

Sliding Minimum Element

長さ $N$ の数列 $a_1, a_2, a_3, ... , a_N$ と整数 $L$ が与えられます。長さ $L$ の連続する部分列すべてについて、各部分列の中の最小の要素を先頭から順番に報告してください。例えば、数列が $\{1, 7, 7, 4, 8, 1, 6\}$ で、$L$ が 3 の場合、長さ $L$ の部分列は $\{1, 7, 7\}$, $\{7, 7, 4\}$, $\{7, 4, 8\}$, $\{4, 8, 1\}$, $\{8, 1, 6\}$ となりますが、それぞれの部分列の最小値となる 1, 4, 4, 1, 1 を先頭の方から順番に出力してください。

Constraints

  • $1 \leq N \leq 10^5$
  • $1 \leq L \leq 10^5$
  • $1 \leq a_i \leq 10^9$

Input

入力は以下の形式で与えられる。

$N$ $L$
$a_1$ $a_2$ ... $a_N$

Output

最小値の列を空白区切りで 1 行に出力せよ。

Sample Input 1

7 3
1 7 7 4 8 1 6

Sample Output 1

1 4 4 1 1