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
Madhav: 2015-01-26 11:37:55

learnt something new known as window sliding!!

Last edit: 2015-01-26 12:00:20
vishal: 2015-01-26 10:00:52

nice question..!!

Abhinandan Agarwal: 2015-01-24 08:51:12

O(n) solution should only be accepted B-)
Made both O(nXk) and O(n)

Last edit: 2015-01-24 08:51:37
vivek singh rana: 2015-01-21 13:44:25

2 dp...enjoyed a lot!!!

kailash: 2015-01-21 10:34:17

window sliding :)

tyler_durden: 2015-01-15 06:52:35

it will be really unfair if you donot solve it in O(n)

Shrihan : 2015-01-08 08:37:53

I am getting a TLE ?

Abhilash: 2014-12-31 07:29:27

put spaces in output

Last edit: 2014-12-31 07:30:26
Vikas: 2014-10-14 17:57:52

Did it in O(N) time :D

rush: 2014-10-12 16:00:00

There are spaces in the 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