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
sgc_072: 2018-01-13 11:50:24

Time limit should be reduced!! Optimised Brute force also getting AC!

shub1025: 2017-12-28 17:44:11

10
2 47 5 2 6 9 87 4 55 466
3
try this out

dunjen_master: 2017-12-27 21:16:42

make sure you write s.erase(s.find(a[i-k])) where s is a multiset otherwise all the occurences of a[i] will be deleted...costed me a WA

dsri_99: 2017-12-23 06:30:25

simple idea of arrays and selection sort is enough to solve the problem.

karthik1997: 2017-12-16 19:48:25

Using Deque with fast i/o gives u AC with 0.00s time . But Also solve it with segment trees etc :)

arjun8115: 2017-10-06 07:29:24

easily solved using set and map...

hitman007: 2017-09-25 21:01:59

I can see lots of people using deque and segment tree. You can try to implement it using sparse table as well (although not best example of it) https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Sparse_Table_(ST)_algorithm

mahilewets: 2017-09-05 15:40:56

std::multiset

hwojtowicz: 2017-08-23 09:58:50

What is definition for contiguous subarray in this case?
Why we got duplicates of '5' in task description test (there is no 3 times of '5' in input array)?

raichu7: 2017-07-30 03:46:37

Compilation error-->AC :)


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