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
Ashish: 2013-12-16 23:37:14

Got TLE with O(nk)... finally AC .. phew!!!

SanchitK: 2013-12-14 10:43:40

getting WA in 5th test case

anonymous: 2013-12-08 15:27:33

o(n) soln runs slower than o(n*k)
Mostly because of STL

~!(*(@*!@^&: 2013-12-08 04:27:25

There are problems if you read input by a fast in/out procedure. It costs many WAs.

Last edit: 2013-12-08 04:59:06
Shashank Gupta: 2013-11-10 05:48:13

Okay I found an O(n) DP solution but it runs even slower than optimized O(n*k). xD My first O(n*k) solution gave me 0.18 and DP O(n) solution gave me 0.20. (C language)

Last edit: 2013-11-10 05:57:14
Shashank Gupta: 2013-11-10 00:53:18

I solved it but I wonder if there is a faster way than O(n*k)?

Priyanshu Srivastava: 2013-09-02 16:28:29

0.18 s using brute force!!

CoNtRaDiCtIoN: 2013-09-01 13:12:32

thank you garima !!!

Abhimanyu: 2013-08-02 07:13:21

any special test cases please ???

innovolt: 2013-07-31 13:15:19

simple ques. did it in 0.19 sec no special algo required think simple.....


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