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
xceptor: 2015-09-09 00:00:27

F***ing Brute force accepted !

Harsh Vardhan Ladha: 2015-08-30 15:18:11

used Deque and sliding window concept..
AC in one go.
O(n)

Last edit: 2015-08-30 15:18:34
kobe24: 2015-08-24 18:35:03

Better do with Sliding Window instead of Segment Trees to learn something

kamran siddique: 2015-08-20 09:35:51

so simple ...

gaurav117: 2015-08-18 15:18:50

brute force with optimizations work good!!!

magare: 2015-08-16 19:55:42

i keep getting NZEC for python solution. works otherwise. please tell me any spaces in the input.

Anmol Varshney: 2015-08-16 13:32:58

My 100th :D

abhijeet: 2015-07-25 15:11:57

O ((n+k )log k)

xxbloodysantaxx: 2015-07-17 16:52:15

Sliding Window , Dont waste time trying to brute force! Even if it works you miss something!!
Even Segment Tree will work!
Even Sparse Table works!
Even Bit will work!!
But this problem teaches the nice Sliding Window algorithm!!

jas.py: 2015-07-14 12:44:20

Few 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
(Copied from a comment on page 11(had go really far)...were useful to me)


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