Given an array aa, a sliding window of size kk is moving from the very left of the array to the very right. Each time the sliding window moves right by one position. For each sliding window position return minimum value of all numbers inside the sliding window.

Implement a function sliding_window_min(a, k) which returns a list of minimums for each sliding window position.

Input data:

First line consists of two numbers: nn - array size (n150000n150000) and kk (k10000k10000). Second line consists of nn numbers - array aa.

Output data:

Minimums in separate lines.

Example:

Input:Input:

6 3

1 3 4 5 2 7

Output:Output:

1

3

2

2

To satisfy time limit for this task your solution has to work for O(n)O(n) . To find hints how to achieve this time complexity estimation watch again screencast about queue implementation and think about how to use queue for this task and how to extract minimum from queue for O(1)O(1) .