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
soumith: 2017-02-11 07:15:52

Last edit: 2017-02-11 07:16:28
kshitij tripathi: 2017-02-04 09:08:34

using deque : 0.01 s , bruteforce : 0.80s :D

aman_joshi668: 2017-01-20 14:19:55

got ac with segment tree but
can someone share o(n)code mail me to anon@gmail.com

Last edit: 2022-06-26 15:51:24
vunnamtej: 2017-01-10 12:54:16

O(n) deque 0.04s

sandeep_4141: 2017-01-06 16:35:59

brute force and deque both are accepted but brute force is easy!!

Last edit: 2017-01-06 17:35:44
sidpatki: 2017-01-03 07:12:15

how can i see others source code?

madhavgaba: 2016-12-28 09:32:38

did using segtree.......how to do with #sliding window?

chinmay0906: 2016-10-28 20:04:30

brute force works but use deque to learn something new ;-)

ani_geek9654: 2016-10-10 22:30:48

SEGMENT TREE ROCKS WUHUU :P

davidgalehouse: 2016-10-03 04:51:17

Note to C# solvers: Input is formatted incorrectly, use RemoveEmptyEntries.


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