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
arp_ee: 2015-04-15 21:37:15

better time through sparse table !!

Last edit: 2015-04-15 21:37:37
Abhay: 2015-04-13 13:14:47

@Shubham Bansal: Use multiset instead of set.

D Pratap : 2015-04-09 13:46:50

Got ACC for O ( N logK)

Shubham Bansal: 2015-03-28 06:29:55

i was trying to solve dis ques using set stl, showing correct answer for all the test cases i can think of, but showing wrong answer..

RAJDEEP GUPTA: 2015-03-27 19:38:04

While solving using JAVA, it gave me NZEC when used BufferedReader for taking inputs. Got AC using Scanner class and O(n) algo.

Indian Cyber Army (IndiShell): 2015-02-10 09:45:45

ac in 1 go with brute force .. !

Nikhil Agarwal: 2015-01-28 12:32:36

those getting wrong answer in 5 add spaces between integers

Madhav: 2015-01-26 11:37:55

learnt something new known as window sliding!!

Last edit: 2015-01-26 12:00:20
vishal: 2015-01-26 10:00:52

nice question..!!

Abhinandan Agarwal: 2015-01-24 08:51:12

O(n) solution should only be accepted B-)
Made both O(nXk) and O(n)

Last edit: 2015-01-24 08:51:37