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
code_aim: 2017-07-01 19:48:26

0.01s

iceelement: 2017-06-30 10:33:22

AC in one, using dp and deque

mangalnimish: 2017-06-29 13:19:39

Wrong answer on judge 5..Please help

itachi_2016: 2017-06-23 21:56:07

Used segtree and got AC but 0.07s not nice though

sagnik_66: 2017-06-01 12:47:55

Interesting problem... 1st used Brute Force, Then used DP in O(n)!

arvind002: 2017-05-31 22:18:54

Try using Deque.
O(n) Deque .02s
O(n*k) sliding Window .02s

ashu121: 2017-03-24 22:04:28

ac in one go
simple implementation of sliding window !!

rohit9934: 2017-03-08 15:54:05

Brute Force worked, i wasnt expecting that because time complexity was O((n-k)*k).Accepted appeared like Magic.

nilabja16180: 2017-03-01 19:06:47

Great application of Deque!
AC in one GO!

vladimira: 2017-02-27 20:38:14

When k<= 3 brute force is faster, this optimization speed up my solution at 15%. About NZEC in python. Read input in such way: >>>words = sys.stdin.read().split() >>>n=int(words[0]) >>>k=int(words[-1]) >>>lst=map(int,words[1:n+1])


Added by:priyamehtanit
Date:2012-02-09
Time limit:0.222s-0.972s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own