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
diablo: 2012-05-28 04:59:55

same here! all test here cases work but gives wrong answer in the fifth one

Abhishek Sharma: 2012-05-24 12:39:03

My program works for every test cases(in question and posted in comments) ;But i am getting WA. Can anyone provide me some more critical test cases ..??

coading: 2012-04-21 08:30:46

i m using 2 for loops for sorting & it showing "TLE" any suggestions.....

Anand: 2012-04-08 00:28:11

6

1 2 4 5 2 1
3
I am able to get correct answer for it. but still the fifth test case fails!!!

ramaravind: 2012-04-02 06:45:43

@ram:check for the following test case
6

1 2 4 5 2 1
3

Last edit: 2012-04-02 06:46:06
ram: 2012-04-01 10:46:39

am getting WA in the fifth test case :( where exactly be the spaces ..

♘Prabhat: 2012-03-29 12:01:46

Last edit: 2014-03-24 17:10:41
aragon: 2012-03-05 12:52:06

Yes,there are spaces in the output.

mynameborat: 2012-02-27 23:09:58

are there spaces in the o/p?

Rishi Mukherje: 2012-02-24 10:43:18

I think there is some problem...I am getting NZEC with python..please tell me about the spaces in the input...or output..


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