## 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
 < Previous 1 2 3 4 5 6 7 8 9 10 11 Next > yaseenmollik: 2019-04-20 19:59:28 Got accepted using SQRT Decomposition! aj_254: 2019-04-03 19:08:27 python users segment tree tle ,use deque or dp .. i optimised to core for segment tree still tle starc_208: 2019-02-01 17:55:53 even brute force got accepted!! marethyu1: 2019-01-01 20:49:23 That's weird, I considered a brute force approach and I got AC on my first attempt. jmr99: 2018-10-13 15:06:14 Way of solving !! 1.dque - 0.03 2.BF - 0.02 3.priority Q - 0.02 4.segment tree - 0.02 5.Use Self-Balancing BST O(nlogK) Last edit: 2018-10-13 15:07:28 phoemur: 2018-09-19 02:12:22 Solved with C++ using: 1-) Brute force: 0.55s 2-) Segment Tree: 0.02s Conclusion: This would be a much better problem if tests where tighter and Brute force did not get AC dia_aj0011: 2018-09-17 14:45:36 solved it with vectors it took 0.54s dewa251202: 2018-08-09 08:52:30 using priority_queue, 0.02 sec + fast io, 0.01 sec Last edit: 2018-08-09 08:54:24 surbhikohli: 2018-07-23 09:25:54 Can the array elements in the input be either space or line separated.(I found some test cases on spoj toolkit where inputted array elements are line separated but here in problem description,array elements in input are space separated .) 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

 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