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
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.

sneh sajal: 2016-04-02 15:00:03

STL :)

prateek1985: 2016-02-14 16:01:32

Learned Deque but stil getting NZEC

pvsmpraveen: 2016-01-27 16:15:49

Done with Segment Trees.

kanishk19: 2016-01-22 14:59:23

Don't forget to put space between output. Cost me 2 WA.

abhigupta4: 2015-11-04 10:41:16

Brute Force(Sliding window only) without any optimization accepted

Last edit: 2015-11-04 11:00:20
Akshay Damle: 2015-10-16 23:47:58

Python solution gets NZEC but same logic in C++ works. Probably weird input format.

shantanu tripathi: 2015-09-26 10:19:19

Last edit: 2015-09-26 10:19:34
arabh_20: 2015-09-24 15:56:52

use tokenization...

Ravi Chandra: 2015-09-16 09:10:37

Got 0.86s on first sub.After some optimizations its 0.02s


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