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
natsu: 2013-05-13 03:55:53

used O(nk) with slight modifications
got AC finally after 8 wa

Code Geass: 2013-05-10 09:54:10

my code is giving wrong answer after 5th test case even it is working correctly on all test cases.....

Atul Kashyap: 2013-04-04 16:39:32

getting wa after 5th test case....even though not printing space after last o/p...

Indrajit Sarkar: 2013-03-29 06:04:58

Be careful with spaces.
Dont give space after the last output

Man Mohan Mishra: 2013-03-21 20:53:48

awesome problem !!
application of recently learnt data structure for me :)

Sundaravel V: 2013-02-23 16:56:16

am getting tle :( after running(5)

Sundaravel V: 2013-02-23 16:55:08

got stuck in in tle after 5th judging!!:( any one help me

Last edit: 2013-03-15 19:20:05
Rajnikanth: 2013-02-21 18:16:32

finally AC.....after 4 WA and 4 TLE

Inspiron: 2013-02-19 19:17:01

AC

tarun sharma: 2012-12-07 04:10:04

getting tle in 5th test case....?


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