ARRAYSUB - subarrays


Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Input

the number n denoting number of elements in the array then after a new line we have the numbers of the array and then k in a new line

n < 10^6
k < 10^5
1 <= k <= n

and each element of the array is between 0 and 10^6

(Edited: In fact, n <= 10^5)

Output

print the output array

Example

Input:
9
1 2 3 1 4 5 2 3 6
3

Output:
3 3 4 5 5 5 6

hide comments
Surya kiran: 2012-02-11 05:20:37

why am i getting WA though my outout is correct ...is there any space between two adjacent elements of output array??

priyamehtanit : 2012-02-11 05:20:37

all others were tle

priyamehtanit : 2012-02-11 05:20:37

after rejudge out of 59 submissions only 5 remain :P huh


Added by:priyamehtanit
Date:2012-02-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own