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


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

hide comments
abhijeet: 2015-07-25 15:11:57

O ((n+k )log k)

xxbloodysantaxx: 2015-07-17 16:52:15

Sliding Window , Dont waste time trying to brute force! Even if it works you miss something!!
Even Segment Tree will work!
Even Sparse Table works!
Even Bit will work!!
But this problem teaches the nice Sliding Window algorithm!!

jas.py: 2015-07-14 12:44:20

Few test cases :
7
1 2 8 4 5 2 3
3
8 8 8 5 5

7
1 2 8 4 5 2 3
4
8 8 8 5
(Copied from a comment on page 11(had go really far)...were useful to me)

Liquid_Science: 2015-06-25 17:07:46

Segment tree & brute force with optimisations both gives tle in java -_-

finally ac with dp:) O(n)

Last edit: 2015-06-26 11:10:38
Aman Parashar: 2015-06-25 11:26:47

This is bad !! Brute force should not work but works !! O(nk) - no way !!
For a non increasing array it should give TLE !!

Last edit: 2015-06-25 11:32:24
Deepak Singh Tomar: 2015-06-23 21:07:56

segment tree works fine

SangKuan: 2015-06-20 09:53:19

ac in first by dp.must has other better way

Ooo....: 2015-06-15 21:58:14

my 150th on spoj =D

burninggoku: 2015-06-14 22:23:43

recursion rejected....set rejected...brute force accepted.... my 23.56th !!!

sujit yadav: 2015-06-13 13:41:45

submit with c++14 compiler coz c++ 4.3.2 gave me TLE for the same solution . simple brute force ..dont forget spaces between integers .

Last edit: 2015-06-13 13:45:02