8648: DSL_3_D : Sliding Minimum Element
[Creator : ]
Description
For a given array $a_1,a_2,a_3,...,a_N$ of N elements and an integer L, find the minimum of each possible sub-arrays with size L and print them from the beginning.
For example, for an array {1,7,7,4,8,1,6} and L=3, the possible sub-arrays with size L=3 includes {1,7,7}, {7,7,4}, {7,4,8}, {4,8,1}, {8,1,6} and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.
For example, for an array {1,7,7,4,8,1,6} and L=3, the possible sub-arrays with size L=3 includes {1,7,7}, {7,7,4}, {7,4,8}, {4,8,1}, {8,1,6} and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.
Input
The input is given in the following format.
$N\ L$
$a_1\ a_2\ ...\ a_N$
$N\ L$
$a_1\ a_2\ ...\ a_N$
Output
Print a sequence of the minimum in a line. Print a space character between adjacent elements.
Constraints
$1≤N≤10^6$
$1≤L≤10^6$
$1≤a_i≤10^9$
$L≤N$
$1≤L≤10^6$
$1≤a_i≤10^9$
$L≤N$
Sample 1 Input
7 3
1 7 7 4 8 1 6
Sample 1 Output
1 4 4 1 1