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
hitman007: 2017-09-25 21:01:59

I can see lots of people using deque and segment tree. You can try to implement it using sparse table as well (although not best example of it) https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Sparse_Table_(ST)_algorithm

mahilewets: 2017-09-05 15:40:56

std::multiset

hwojtowicz: 2017-08-23 09:58:50

What is definition for contiguous subarray in this case?
Why we got duplicates of '5' in task description test (there is no 3 times of '5' in input array)?

raichu7: 2017-07-30 03:46:37

Compilation error-->AC :)

code_aim: 2017-07-01 19:48:26

0.01s

iceelement: 2017-06-30 10:33:22

AC in one, using dp and deque

mangalnimish: 2017-06-29 13:19:39

Wrong answer on judge 5..Please help

itachi_2016: 2017-06-23 21:56:07

Used segtree and got AC but 0.07s not nice though

sagnik_66: 2017-06-01 12:47:55

Interesting problem... 1st used Brute Force, Then used DP in O(n)!

arvind002: 2017-05-31 22:18:54

Try using Deque.
O(n) Deque .02s
O(n*k) sliding Window .02s


Added by:priyamehtanit
Date:2012-02-09
Time limit:0.222s-0.972s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own