Sliding Window Maximum

You are given an array of n integers and an integer k. Your task is to find the maximum element in every contiguous subarray (window) of size k in the given array.

If k is greater than n, output nothing.

For example, if the input array is [1, 3, -1, -3, 5, 3, 6, 7] and k is 3, the output should be [3, 3, 5, 5, 6, 7] because:

• Maximum of [1, 3, -1] is 3
• Maximum of [3, -1, -3] is 3
• Maximum of [-1, -3, 5] is 5
• Maximum of [-3, 5, 3] is 5
• Maximum of [5, 3, 6] is 6
• Maximum of [3, 6, 7] is 7

The sliding window algorithm can be implemented in O(n) time using a double-ended queue. The mathematical formulation of the problem is as follows:

Given an array \( A = [a_1, a_2, \dots, a_n] \) and a window size \( k \), find a sequence \( M = [m_1, m_2, \dots, m_{n-k+1}] \) such that \( m_i = \max\{a_i, a_{i+1}, \dots, a_{i+k-1}\} \) for \( i = 1, 2, \dots, n-k+1 \).

inputFormat

The input is read from standard input (stdin) and has the following format:

n k
a1 a2 a3 ... an

where:

• n is the number of elements in the array.
• k is the size of the sliding window.
• a1, a2, ..., an are the integer elements of the array separated by spaces.

outputFormat

Output the maximum elements for each contiguous subarray (window) of size k in the array. The output should be written to standard output (stdout) as a single line with the numbers separated by a space. If k is greater than n, output nothing.

## sample

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

3 3 5 5 6 7