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 except: SCM chicken
Resource:own

hide comments
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
[Mayank Pratap]: 2015-06-03 13:55:02

Brute force with optimisation .... AC ... :)

Jerry Goyal: 2015-05-29 14:49:07

what's the fuss about?..simple bruteforce.

saurabh: 2015-05-26 16:45:06

Phew ..Got AC..After many WA...

Last edit: 2015-05-26 17:06:01