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
bhavika2000: 2020-04-08 20:53:57

what is the 5th testcase?

ajaygupta007: 2020-04-07 12:44:43

use deque to store index.

mansi_m: 2020-04-02 06:56:47

i did my solution in java using deque
getting NZEC
can anyone help
mail me i'll show my code(iwanttoencouragecheating@iisuniv.ac.in)

Last edit: 2022-06-26 15:53:53
seastian: 2020-03-29 16:00:26

weak TC
acc in O(n*K)

geek_goku6: 2020-03-28 10:09:09

I have done this using dequeue but if someone has done it using segment tree then please send it to me at anon@gmail.com since i am trying to practice more on segment tree. Thanks! :)

Last edit: 2022-06-26 15:52:58
hitesh87: 2020-03-19 10:18:40

cin/cout --> 0.16s
pf/sf --> 0.02s

sumit_kushwah: 2020-03-02 20:22:29

segment tree DS also provide a better solution

mrmajumder: 2020-02-11 07:05:45

Double ended queues are the way to go!
O(n) solution therefore

codercodecoder: 2020-01-30 16:16:59

dp in python ac in one go

rahulrawat09: 2019-11-30 09:24:51

https://www.youtube.com/watch?v=39grPZtywyQ


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