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
sohelr360: 2024-05-20 18:13:56

You can solve it using monotonic queue in O(n).

tobiasveiga: 2023-12-10 13:04:12

n <= 10^5 did not work for me. My solution only got accepted when I used n < 10^6

uditmehra_827: 2023-10-19 04:39:53

do anyone have an approach without using set, multiset, i mean not using advantages of ds like multiset..?

mostafaasey25: 2022-06-26 11:07:58

my solution i hope its help : )
<snip>
[Simes]: No thanks. With 8500+ AC users what makes you think people want this?

Last edit: 2022-06-26 15:48:34
manoj0606: 2022-03-21 13:22:04

Simple solution using policy based ds in c++ :)

yasser1110: 2021-07-23 16:03:48

Really interesting problem. Learned tons from it. Solved it using c++ map. Because its implemented as a red black tree, we have O(logn) inserts, lookups and deletes.

h4ck3rsh4d0w: 2021-06-23 15:52:24

AC in one go (used Max heap)

nitin_20: 2021-05-09 03:48:18

Max of every k element

kimg: 2021-02-10 16:45:56

Simple brutefoce works.
Use max_element in cpp

deerawat: 2021-01-03 10:19:56

Brute force works!


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