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

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


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