Sliding Window Maximum

A window of size k slides over the array from left to right, one position at a time. Print the maximum inside the window at every position.

Input:

• line 1: n k
• line 2: n integers

Output: n − k + 1 numbers on one line — the maximum of each window.

Constraints: 1 ≤ k ≤ n ≤ 10⁵, −10⁴ ≤ a[i] ≤ 10⁴.

Think about it: recomputing each window is O(n·k) — too slow when k is large. Keep a deque of indices whose values are decreasing; the front is always the current maximum. Every index enters and leaves once: O(n).