Sphere Online Judge



SPOJ Problem Set (classical)

10582. subarrays

Problem code: ARRAYSUB

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
2015-01-26 11:37:55 Madhav
learnt something new known as window sliding!!

Last edit: 2015-01-26 12:00:20
2015-01-26 10:00:52 vishal
nice question..!!
2015-01-24 08:51:12 Abhinandan Agarwal
O(n) solution should only be accepted B-)
Made both O(nXk) and O(n)

Last edit: 2015-01-24 08:51:37
2015-01-21 13:44:25 vivek singh rana
2 dp...enjoyed a lot!!!
2015-01-21 10:34:17 kailash
window sliding :)
2015-01-15 06:52:35 tyler_durden
it will be really unfair if you donot solve it in O(n)
2015-01-08 08:37:53 Shrihan
I am getting a TLE ?
2014-12-31 07:29:27 Abhilash
put spaces in output

Last edit: 2014-12-31 07:30:26
2014-10-14 17:57:52 Vikas
Did it in O(N) time :D
2014-10-12 16:00:00 rk29
There are spaces in the output.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.