Sliding Window Maximum

Problem statement

A traffic sensor publishes the highest vehicle count in each moving block of k readings. The reporting window advances one reading at a time, dropping its oldest entry and including the next one. Your task Return the maximum value in every contiguous window of length k, in left-to-right order. Important details There are n-k+1 answers. Repeated maximum values must be handled even when one copy leaves the window. Use O(n) time with a deque of candidate indices; output each maximum, not its position. Worked example For readings [2, 5, 1, 4] and k = 2, the windows have maxima 5, 5 and 4. Print 5 5 4.

Input format

First line: n k. Next line: n readings.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

1 <= k <= n <= 100000; -10000 <= values <= 10000.

Sample input

4 2
2 5 1 4

Sample output

5 5 4