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
kanishkverma_1: 2020-11-28 16:05:47

Java users , Use TreeMap . Works like a charm . Complexity = O(nlogn),

sujeet_22: 2020-10-12 19:27:05

I simply applied segment tree...xD.

kapilsukrit2: 2020-09-28 10:11:38

Try these 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

Thanks to @jas.py (page 11) for these :)

distructo: 2020-09-22 22:10:37

Simple bruteforce works

stergen007: 2020-09-07 06:07:47

Once try this case in my case I got WA on test case 5 and this is test case 5, Bruteforce is acceptable, In my case I solved in Bruteforce approach and got accepted

12

1 2 3 3 1 2 4 5 1 1 2 3

3

Your output:3 3 3 2 4 5 5 5 2 3

Expected output: 3 3 3 3 4 5 5 5 2 3

vishesh_iit: 2020-08-12 12:26:49

what's he intuition behind using the deque

adityarajiv: 2020-08-03 15:35:34

getting wrong answer on test case 5 please help

relllik: 2020-07-03 02:52:32

sqrt decomposition
cin/cout -> 0.14 s
printf/scanf -> 0.12 s

fawad: 2020-06-29 11:39:35

I was learning two pointer method. AC in one go. 0.06 time solution

israkul9: 2020-05-25 13:17:57

got Ac using slidding window technique and multiset

Last edit: 2020-05-25 13:18:14

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