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

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

hide comments
2013-07-22 20:44:37 Rana Saha
Good one! .. No special Algo required .. And yes int works fine ..
2013-07-19 17:50:51 ***
finally!!! got AC!!!

Last edit: 2013-07-19 17:52:28
2013-07-10 08:49:47 ankit kumar sinha
5th test case????
please
2013-06-29 16:33:29 pika_pika
Python 2.x or 3.x gives a stupid error of indentation which is syntactically correct yet the spoj engie goes crazy
2013-06-25 06:54:24 Himanshu
0.19 AC in one go!!
yippy
2013-06-23 21:05:50 Aditya Pande
0.10 sec in optimized O(nk)
surprised myself

Last edit: 2013-06-24 06:08:01
2013-06-23 08:40:53 Shashank_Jain
Simple DP in O(n) and AC ! baam !
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.