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
rv111: 2018-07-15 19:00:45

why deque is taking so much time ie.. 0.51 seconds...
can anyone pls check - https://ideone.com/FqEWJp

sanyam19: 2018-06-19 05:45:27

easy1... :)

wrzoboo: 2018-05-28 12:32:49

python 3 bruteforce using max() per each subarray gives TLE, you need to write something better ;-)

aakash2509: 2018-05-26 12:39:07

Cakewalk for C++. Can be solved just with an array and max_element() function.

a161112225: 2018-05-17 10:06:47

use seg tree got AC in one go! but 0.04......

arunikacs16: 2018-05-12 09:00:32

Can anybody tell me why am I getting a compile time error in my code when it compiles well on the system

anirudnits: 2018-05-11 15:52:50

I mistakenly printed the answers in separate lines and not in a single line like in the sample cases but still got AC!!

coderslegacy: 2018-04-23 22:49:24

use multiset

vipulyadav150: 2018-03-03 20:31:16

NO NEW CONCEPT !AC IN ONE GO!!!
@aacool

aaacool: 2018-03-03 16:13:41

AC in 1 GO!!!


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