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
2012-10-24 16:24:40 aristofanis
does an O(nk) solution pass?
Answer: no, you have to use a special data structure


Last edit: 2013-02-20 16:13:39
2012-10-01 12:37:15 Ravi Kumar
not even a single submission in python...why??
2012-07-08 12:32:01 Romal Thoppilan
Please improve on your testcases .. and rejudge
2012-07-02 18:29:13 mahesh
@ priyamehtanit... check my code.. its segsev in 5th test case.c my id is 7249031
2012-07-02 18:29:12 mahesh
@ priyamehtanit... check my code.. its segsev in 5th test case.c my id is 7249031
2012-07-02 18:27:01 mahesh
while 5th test case running its showing as segmentation fault.. any one knows why??
2012-06-26 08:49:07 spock
OMG...finally.. :

well brute force or any modifications to it won't work. you have to think of a data structure to hold these values.

Last edit: 2012-06-30 12:19:07
2012-06-01 08:15:37 vishal chaudhary
OKAY....:)
2012-06-01 06:15:17 :D
Obviously case like N=K=10 meets all three constraints. And don't use "what the hell" just because you didn't understand the problem. Be polite!
2012-05-31 18:20:23 vishal chaudhary
question says that...n<10^6 and ..k<10^5.
then why is "=" in the line..1 <= k <=n b/w k and n...:\

Last edit: 2012-06-01 08:13:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.