ARRAYSUB - subarrays

no tags 

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

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
alok singh: 2016-07-16 14:32:43

AC in 1>>>>>>>

xinnix: 2016-07-10 07:37:06

love STL

sonali9696: 2016-07-05 22:10:21

Test Case: 9

3 2 1 1 1 3 4 5 6
3
O/P: 3 2 1 3 4 5 6
PS: Simple sliding window

Last edit: 2016-07-05 22:11:13
wesolyfoton: 2016-06-26 05:03:42

Beatiful! Try to solve this problem in O(n) to learn something new.

Sourabh Goel: 2016-06-16 19:06:00

multiset rocks. hint: erase the lower bound of number

a2hksy: 2016-06-13 11:05:54

:)

subodra_9: 2016-06-02 14:19:36

AC in 1 go

karthik1997: 2016-05-28 12:50:56

Knew O(n*k) , O(nlogn), O(nlogk) ,and finally learnt an O(n) approach . :p . Sliding window and deque are the best

praval_singhal: 2016-05-08 07:23:36

My 50th. Solved in O(n). :)

Jawahar R: 2016-04-21 15:00:30

If you are using multiset in C++, note that erase(number) function in multiset erases all the instances of that number in the multiset.


Added by:priyamehtanit
Date:2012-02-09
Time limit:0.222s-0.972s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own