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
Vipul Pandey: 2013-06-14 13:40:42

no use of any data structure.

Amitayush Thakur: 2013-06-03 07:17:57

My code runs fine on http://ideone.com/
It works for all test cases
I have given correct spacing between the output
But still I am getting runtime error (NZEC) .
Plz suggest me something.I have used Python 2.7 as programming language.

vigneshwaran M: 2013-06-02 18:58:10

pls post tat 5th test case...

Kumar Mrinal: 2013-05-27 16:38:59

Segment tree works fine ...

!!AV!!: 2013-05-25 08:53:47

Little Modification to Range Minimum query and AC..
and yes there are spaces between the output numbers... :)

Spar!k: 2013-05-20 22:53:11

set is enough

Sudhanshu Shekhar: 2013-05-20 18:52:28

I got AC using Deque and Set but Segment Tree is timing out. Anyone any idea how to get around this?

Last edit: 2013-05-20 18:52:55
pankaj bhardwaj: 2013-05-17 12:58:36

can this be solved other than segmented tree ??

Atul Kumar Verma: 2013-05-17 12:03:53

Finally AC after many TLE nice ques. :)

Noob: 2013-05-16 21:13:33

Test case Pls :|
getting correct output for as many case given and plenty of random cases.no error of spaces. and what not.
i am not getting AC


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