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

hide comments
saurabh: 2015-05-26 16:45:06

Phew ..Got AC..After many WA...

Last edit: 2015-05-26 17:06:01
Shubham Bansal: 2015-05-23 21:29:35

finally O(n) :-). caused a lot of wa due to silly mistakes. same question came at MAY'15 codechef long challenge.

excursionist: 2015-05-15 18:00:15

AC in first go :D
made my day ;)

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


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