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
jasbir_220b2: 2016-08-18 20:20:22

brute force accepted..

vaibhav goyal: 2016-08-17 09:29:31

done this question by 4 different ways :)
1) brute force -O(nk)
2)using segment tree - O(nlogn)
3)using multiset(stl) - O(nlogk)
4) using deque - O(n)
:D

vaibhav goyal: 2016-08-17 08:44:25

weak test cases even O(nk) solution will also be accepted !! :D

alok singh: 2016-07-16 14:32:43

AC in 1>>>>>>>

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

love STL

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


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