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
shikhar_may7: 2019-11-06 07:14:31

deque will help you out...!!!

coder1971: 2019-10-22 11:18:40

It can be solved using brute force as though it's complexity is o(n^2)

jojo9910: 2019-10-17 17:11:23

solved using hash map:
time::0.08

invinsible: 2019-09-29 16:11:38

Same logic AC when scanner is used but Runtime error when BufferedReader is used.

scolar_fuad: 2019-08-15 08:04:17

nlog(n) solution using priority queue datastructure ....

Nice problem on sliding window problem

hetp111nu: 2019-08-09 09:09:21

brute force works... try it in O(n)

sajal6689: 2019-07-30 19:11:39

Last edit: 2019-08-10 08:04:44
yogesh1208: 2019-07-30 14:06:55

using java it is giving NZEC using brute force

shahayush457: 2019-06-19 07:05:42

Just use multiset instead of a set...costed me a runtime error .

yaseenmollik: 2019-04-20 19:59:28

Got accepted using SQRT Decomposition!


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