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
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!

kanishkverma_1: 2020-11-28 16:05:47

Java users , Use TreeMap . Works like a charm . Complexity = O(nlogn),

sujeet_22: 2020-10-12 19:27:05

I simply applied segment tree...xD.

kapilsukrit2: 2020-09-28 10:11:38

Try these test cases
7
1 2 8 4 5 2 3
3
8 8 8 5 5

7
1 2 8 4 5 2 3
4
8 8 8 5

Thanks to @jas.py (page 11) for these :)

distructo: 2020-09-22 22:10:37

Simple bruteforce 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