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

xceptor: 2015-09-09 00:00:27

F***ing Brute force accepted !

Harsh Vardhan Ladha: 2015-08-30 15:18:11

used Deque and sliding window concept..
AC in one go.
O(n)

Last edit: 2015-08-30 15:18:34
kobe24: 2015-08-24 18:35:03

Better do with Sliding Window instead of Segment Trees to learn something


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