You are given an array of n integers and a window length k. A window is a block of k consecutive elements. Sliding the window from the left edge to the right edge produces exactly n - k + 1 windows. For each window, report the largest element it contains.
Output the window maxima in order, from the leftmost window to the rightmost.
Input format
Line 1: two integers n and k separated by a space.
Line 2: n space-separated integers, the array values.
Output format
A single line with the n - k + 1 window maxima, separated by single spaces, in left-to-right order.
Constraints
- 1 ≤ k ≤ n ≤ 100000
- -1000000000 ≤ each value ≤ 1000000000
- The answer is uniquely determined: each window has exactly one maximum value.