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
(Tjandra Satria Gunawan)(曾毅昆): 2014-07-16 22:31:02

I don't know O(n) solution for this problem yet, but my O(n*log n) is 0.03s :-P

Last edit: 2014-12-29 13:55:17
zicowa: 2014-07-16 20:45:02

Hello Coders !!
I know you all are doing great !!
O(nlog(n)) solution can be easily think for this problem but there exists a O(n) solution for this problem think for O(n) solution you will surely learn something my last submission is on the same algo . and you dont believe it is the smallest code among all :D

Last edit: 2014-12-29 13:55:34
Saurav Sharma: 2014-07-01 08:43:30

brute force method get rejected

agaurav77: 2014-05-31 15:57:02

Good Question! O(n*k) definitely works, but remember not to make your code O(n*k) for all cases. It should be worst case O(n*k).

free mind ;): 2014-04-14 20:33:59

done in 0.09 with O(n*k) finally !

Vlad Mosko: 2014-03-02 18:26:46

NlogN is really easy.

appy: 2014-01-11 21:13:53

anyone help with the whitespaces in input
e.g
9
<--- this white space
1 2 3 1 4 5 2 3 6
please and is there space or \n after the last output?????

appy: 2014-01-11 17:10:55

is there any whitespace means after
9
<--- this line
i m getting wrong answer again and again...please sum1 help

shashank: 2014-01-05 21:06:00

Interesting Same implementation in java got NZEC but in C++ got AC ....
Sometimes java sucks ....

pika_pika: 2013-12-31 15:32:09

those who are getting WA in the 5th test case try cases with k = 1
eg
5
2 8 4 3 6
1
worked for me considering this.


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