Task

Given an array of integers and window size w, return the minimum value in each contiguous subarray of length w. Use a monotonic deque for O(n).

Input

• Line 1: two ints n w
• Line 2: n space-separated ints

Output

n - w + 1 space-separated integers on one line.

Example

Input:

6 3
3 1 2 5 4 6

Output:

1 1 2 4

Scaffolding

def window_min(arr: list[int], w: int) -> list[int]: ...

Notes

Track E: stdlib only — use collections.deque. Maintain a monotonic increasing deque of indices: pop from back when new value ≤ tail; pop from front when index is out of window.