Sliding Window Maximum

Hard#queue #deque #sliding-window· solved by 0 · time limit 2.0 s

For every window of $k$ consecutive elements, print its maximum. Use a deque to get $O(n)$ overall.

Input

$n$ , then $n$ integers, then $k$ .

$n-k+1$ maxima.

$1 \le k \le n \le 2 \times 10^5$

Input

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

Output

3 3 5 5 6 7