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:1s-4s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:own

hide comments
2014-10-23 23:28:18 Rajat (1307086)
F**k. Ans has spaces. This gave me several wrong answers.
2014-10-23 23:28:02 Rajat (1307086)
F**k. Ans has spaces. This gave me several wrong answers.
2014-10-14 17:57:52 Vikas
Did it in O(N) time :D
2014-10-12 16:00:00 xlytron
There are spaces in the output.
2014-10-11 19:35:27 jack sparrow
hash+heap+twopointer=AC :D
2014-10-05 15:02:34 Ayush Vatsa
my brute force +deque solution both got AC'd in 0.2sec.
2014-09-10 13:45:17 surayans tiwari
accepted 0.71 sec segmented trees
2014-08-29 14:33:25 Pallav Goyal
I think that the numbers of the array are negative too in the test cases. Gave me several WA's!!!
2014-08-14 20:56:29 Aradhya
why my O(3n) soln is taking so much time ;/

Last edit: 2014-08-14 20:56:46
2014-07-22 12:05:44 VirinchiSamineni
got WA in 5th case can somebody help with this issue
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.