Sliding Window Maximum

Given an integer array and a positive integer k, your task is to find the maximum value in every contiguous subarray (or window) of length k.

The sliding window moves from the beginning of the array to the end and only the elements within the window are considered for the maximum calculation. An optimal solution with O(n) time complexity using a deque data structure is expected.

Note: Input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line contains two space-separated integers n and k, where n is the number of elements in the array and k is the size of the sliding window.

The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single line containing the maximum values for each contiguous subarray of length k, separated by a space.

8 3
1 3 -1 -3 5 3 6 7

3 3 5 5 6 7