Sliding Window Maximum

Given an array of integers and a window size \(k\), your task is to compute the maximum value in every contiguous subarray (or window) of size \(k\). More formally, for an array \(A\) of length \(n\), you need to output an array \(M\) of length \(n-k+1\) such that \(M_i = \max\{A_i, A_{i+1}, \dots, A_{i+k-1}\}\).

It is guaranteed that \(0 \leq n \leq 10^5\) and \(1 \leq k \leq n\) when \(n > 0\). If the array is empty, output an empty line.

Example:

Input:
8 3
1 3 -1 -3 5 3 6 7
Output:
3 3 5 5 6 7

inputFormat

The input is read from standard input (stdin). The first line contains two 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. When (n = 0), the second line will be empty.

outputFormat

Print the maximum of each contiguous subarray of size (k) as a sequence of space-separated integers on a single line to standard output (stdout). If the array is empty, print an empty line.## sample

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

3 3 5 5 6 7