Due to the rise of covid-19 cases in India, this year BCCI decided to organize knock-out matches in IPL rather than a league. 
Today is matchday 2 and it is between the most loved team Chennai Super Kings and the most underrated team - Punjab Kings.  Stephen Fleming, the head coach of CSK, analyzing the batting stats of Punjab. He has stats of runs scored by all N players in the previous season and he wants to find the maximum score for each and every contiguous sub-list of size K to strategize for the game. 
Example 1:
Input:
N = 9, K = 3
arr[] = 1 2 3 1 4 5 2 3 6
Output: 
3 3 4 5 5 5 6 
Explanation: 
1st contiguous subarray = {1 2 3} Max = 3
2nd contiguous subarray = {2 3 1} Max = 3
3rd contiguous subarray = {3 1 4} Max = 4
4th contiguous subarray = {1 4 5} Max = 5
5th contiguous subarray = {4 5 2} Max = 5
6th contiguous subarray = {5 2 3} Max = 5
7th contiguous subarray = {2 3 6} Max = 6
Example 2:
Input:
N = 10, K = 4
arr[] = 8 5 10 7 9 4 15 12 90 13
Output: 
10 10 10 15 15 90 90
Explanation: 
1st contiguous subarray = {8 5 10 7}, Max = 10
2nd contiguous subarray = {5 10 7 9}, Max = 10 
3rd contiguous subarray = {10 7 9 4}, Max = 10 
4th contiguous subarray = {7 9 4 15}, Max = 15
5th contiguous subarray = {9 4 15 12}, Max = 15 
6th contiguous subarray = {4 15 12 90}, Max = 90 
7th contiguous subarray = {15 12 90 13}, Max = 90 
Your Task:  
You don't need to read input or print anything. Complete the function max_of_subarrays() which takes the array, N, and K as input parameters and returns a list of integers denoting the maximum of every contiguous subarray of size K.
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ K ≤ N
0 ≤ arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def max_of_subarrays(self,arr,n,k):

        '''

        you can use collections module here.

        :param a: given array

        :param n: size of array

        :param k: value of k

        :return: A list of required values 

        '''

        #code here

Solutions:
class Solution:

	def max_of_subarrays(self, arr, n, k):
		ans = []
		d = deque()
		for x in range(n):
			while d and arr[d[-1]] <= arr[x]:
				d.pop()
			d.append(x)
			if d[0] == x - k:
				d.popleft()
			if x >= k - 1:
				ans.append(arr[d[0]])
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		q = deque()
		for i in range(k):
			q.append(arr[i])
		mx = max(q)
		ans = []
		ans.append(mx)
		for i in range(k, n):
			t = q.popleft()
			q.append(arr[i])
			if t == mx:
				mx = max(q)
				ans.append(mx)
			elif arr[i] > mx:
				ans.append(arr[i])
				mx = arr[i]
			else:
				ans.append(mx)
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		stack = []
		ans = []
		for i in range(k):
			while len(stack) != 0 and arr[stack[-1]] < arr[i]:
				stack.pop()
			stack.append(i)
		ans.append(arr[stack[0]])
		for i in range(k, n):
			if i - k >= stack[0]:
				stack.pop(0)
			while len(stack) != 0 and arr[stack[-1]] < arr[i]:
				stack.pop()
			stack.append(i)
			ans.append(arr[stack[0]])
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		queue = deque()
		result = []
		for i in range(k):
			if queue:
				while queue and arr[i] > arr[queue[-1]]:
					queue.pop()
			queue.append(i)
		result.append(arr[queue[0]])
		left = 1
		right = k
		while right < n:
			if left > queue[0]:
				queue.popleft()
			if queue and arr[right] > arr[queue[-1]]:
				while queue and arr[right] > arr[queue[-1]]:
					queue.pop()
			queue.append(right)
			result.append(arr[queue[0]])
			left += 1
			right += 1
		return result


class Solution:

	def max_of_subarrays(self, arr, n, k):
		(stack, list1) = ([], [])
		for (i, v) in enumerate(arr):
			while stack and i - stack[0][0] >= k:
				stack = stack[1:]
			while stack and stack[-1][1] < v:
				stack.pop()
			stack.append([i, v])
			if i >= k - 1:
				list1.append(stack[0][1])
		return list1


from collections import *

class Solution:

	def max_of_subarrays(self, arr, n, k):
		(stack, ans) = ([], [])
		for (i, e) in enumerate(arr):
			while stack and i - stack[0][1] >= k:
				stack = stack[1:]
			while stack and stack[-1][0] < e:
				stack.pop()
			stack.append((e, i))
			if i >= k - 1:
				ans.append(stack[0][0])
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		output = []
		dq = deque()
		for i in range(n):
			while dq and arr[dq[-1]] < arr[i]:
				dq.pop()
			dq.append(i)
			while dq[0] <= i - k:
				dq.popleft()
			if i >= k - 1:
				output.append(arr[dq[0]])
		return output


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		q = []
		ans = []
		start = 0
		end = 0
		while end < n:
			while q and q[-1] < arr[end]:
				q.pop()
			q.append(arr[end])
			if end - start + 1 < k:
				end += 1
			elif end - start + 1 == k:
				ans.append(q[0])
				if q[0] == arr[start]:
					q.pop(0)
				start += 1
				end += 1
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		result = []
		window = deque()
		for i in range(n):
			while window and window[0] <= i - k:
				window.popleft()
			while window and arr[window[-1]] < arr[i]:
				window.pop()
			window.append(i)
			if i >= k - 1:
				result.append(arr[window[0]])
		return result


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		ma = []
		q = deque()
		for i in range(k):
			while q and arr[i] >= arr[q[-1]]:
				q.pop()
			q.append(i)
		for i in range(k, n):
			ma.append(arr[q[0]])
			while q and q[0] <= i - k:
				q.popleft()
			while q and arr[i] >= arr[q[-1]]:
				q.pop()
			q.append(i)
		ma.append(arr[q[0]])
		return ma


import heapq

class Solution:

	def max_of_subarrays(self, arr, n, k):
		dp = []
		ans = []
		for i in range(len(arr)):
			if dp and dp[0] == i - k:
				dp.pop(0)
			while dp and arr[i] > arr[dp[-1]]:
				dp.pop()
			dp.append(i)
			if i >= k - 1:
				ans.append(arr[dp[0]])
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		if n == 1 or k == 1:
			return arr
		start = 0
		end = 1
		current_mx = 0
		res = []
		while end < n:
			if arr[end] > arr[current_mx] and current_mx >= start:
				current_mx = end
			elif current_mx < start:
				current_mx = start
				end = start
			if end - start >= k - 1:
				res.append(arr[current_mx])
				start += 1
			end += 1
		return res


def next_greater_element_index(input_arr: [], n):
	output_arr = [float('inf')] * n
	data_stack = []
	for i in reversed(range(n)):
		element = input_arr[i]
		while len(data_stack) > 0 and element >= input_arr[data_stack[-1]]:
			data_stack.pop(-1)
		if len(data_stack) > 0:
			output_arr[i] = data_stack[-1]
			data_stack.append(i)
		else:
			data_stack.append(i)
	return output_arr

def max_sub_array_sum_size_k(input_arr: [], n: int, k: int):
	next_greater_element_index_arr = next_greater_element_index(input_arr, n)
	i = 0
	j = 0
	end = k - 1
	output_arr = []
	while end < n:
		if j < i:
			j = i
		ans = j
		while next_greater_element_index_arr[j] <= end:
			ans = j
			j = next_greater_element_index_arr[j]
		output_arr.append(input_arr[j])
		i = i + 1
		end = end + 1
	return output_arr

class Solution:

	def max_of_subarrays(self, arr, n, k):
		return max_sub_array_sum_size_k(arr, n, k)


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		q = deque()
		res = []
		left = right = 0
		while right < len(arr):
			while q and arr[q[-1]] < arr[right]:
				q.pop()
			q.append(right)
			if left > q[0]:
				q.popleft()
			if right + 1 >= k:
				res.append(arr[q[0]])
				left += 1
			right += 1
		return res


class Solution:

	def max_of_subarrays(self, nums, n, k):
		dq = []
		ans = []
		for i in range(k):
			while dq and dq[-1] < nums[i]:
				dq.remove(dq[-1])
			dq.append(nums[i])
		ans.append(dq[0])
		j = 0
		for i in range(k, n):
			if arr[j] == dq[0]:
				dq.remove(dq[0])
			j += 1
			while dq and dq[-1] < nums[i]:
				dq.remove(dq[-1])
			dq.append(arr[i])
			ans.append(dq[0])
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		j = 0
		i = 0
		a = []
		ans = []
		while j < n:
			while len(a) > 0 and a[-1] < arr[j]:
				a.pop()
			a.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				ans.append(a[0])
				if arr[i] == a[0]:
					a.pop(0)
				i += 1
				j += 1
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		q = []
		res = []
		for i in range(n):
			while len(q) >= 1 and q[-1][0] <= arr[i]:
				q.pop(-1)
			q.append([arr[i], i])
			if i + 1 >= k:
				while len(q) > 1 and q[0][1] <= i - k:
					q.pop(0)
				res.append(q[0][0])
		return res


import heapq

class Solution:

	def max_of_subarrays(self, arr, n, k):
		ans = []
		res = []
		for i in range(k):
			while res and arr[i] >= arr[res[-1]]:
				res.pop()
			res.append(i)
		for i in range(k, n):
			ans.append(arr[res[0]])
			while res and res[0] <= i - k:
				res.pop(0)
			while res and arr[i] >= arr[res[-1]]:
				res.pop()
			res.append(i)
		ans.append(arr[res[0]])
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		lst = [max(arr[:k])]
		for i in range(k, n):
			if arr[i - k] == lst[-1]:
				lst.append(max(arr[i - k + 1:i + 1]))
			elif arr[i] > lst[-1]:
				lst.append(arr[i])
			else:
				lst.append(lst[-1])
		return lst


import collections

class Solution:

	def max_of_subarrays(self, arr, n, k):
		q = collections.deque()
		i = 0
		j = 0
		res = []
		while j < n:
			while q and q[-1] < arr[j]:
				q.pop()
			q.append(arr[j])
			if j - i + 1 < k:
				j += 1
			else:
				if j - i + 1 == k:
					res.append(q[0])
					if arr[i] == q[0]:
						q.popleft()
				i += 1
				j += 1
		return res


from collections import deque

class Solution:

	def max_of_subarrays(self, a, n, k):
		q = deque([])
		ans = []
		for i in range(k):
			while q and a[i] >= a[q[-1]]:
				q.pop()
			q.append(i)
		for i in range(k, n):
			ans.append(a[q[0]])
			if q and q[0] <= i - k:
				q.popleft()
			while q and a[i] >= a[q[-1]]:
				q.pop()
			q.append(i)
		ans.append(a[q[0]])
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		dq = deque()
		ans = []
		for i in range(k):
			while dq and arr[dq[-1]] < arr[i]:
				dq.pop()
			dq.append(i)
		for i in range(k, n):
			ans.append(arr[dq[0]])
			if dq[0] + k <= i:
				dq.popleft()
			while dq and arr[dq[-1]] < arr[i]:
				dq.pop()
			dq.append(i)
		ans.append(arr[dq[0]])
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		Qi = deque()
		a = []
		for i in range(k):
			while Qi and arr[i] >= arr[Qi[-1]]:
				Qi.pop()
			Qi.append(i)
		for i in range(k, n):
			print(str(arr[Qi[0]]) + ' ', end='')
			while Qi and Qi[0] <= i - k:
				Qi.popleft()
			while Qi and arr[i] >= arr[Qi[-1]]:
				Qi.pop()
			Qi.append(i)
		a.append(arr[Qi[0]])
		return a


class Solution:

	def max_of_subarrays(self, arr, n, k):
		a = []
		ans = []
		i = j = 0
		if k == 0 or not len(arr):
			return ans
		while j in range(n):
			while len(a) and a[-1] < arr[j]:
				a.pop(-1)
			a.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				ans.append(a[0])
				if a[0] == arr[i]:
					a.pop(0)
				i += 1
				j += 1
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		deq = deque()
		ans = []
		for i in range(k):
			while deq and arr[i] >= arr[deq[-1]]:
				deq.pop()
			deq.append(i)
		for j in range(k, n):
			ans += [arr[deq[0]]]
			while deq and deq[0] <= j - k:
				deq.popleft()
			while deq and arr[j] >= arr[deq[-1]]:
				deq.pop()
			deq.append(j)
		ans.append(arr[deq[0]])
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		if k == 1 or n == 1:
			return arr
		sta = []
		ans = []
		l = 0
		i = 0
		while i < n:
			if i < k - 1:
				while l > 0 and sta[-1][0] < arr[i]:
					sta.pop()
					l -= 1
				sta.append([arr[i], i])
				l += 1
			else:
				if sta[0][1] <= i - k:
					sta.remove(sta[0])
					l -= 1
				while l > 0 and sta[-1][0] < arr[i]:
					sta.pop()
					l -= 1
				sta.append([arr[i], i])
				l += 1
				ans.append(sta[0][0])
			i += 1
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		(i, j) = (0, 0)
		mx = []
		res = []
		while j < n:
			if len(mx) > 0 and mx[-1] < arr[j]:
				while len(mx) > 0 and mx[-1] < arr[j]:
					mx.pop()
			mx.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				res.append(mx[0])
				if mx[0] == arr[i]:
					mx.pop(0)
				j += 1
				i += 1
		return res


class Solution:

	def max_of_subarrays(self, nums, n, k):
		max_vals = []
		ans = []
		i = j = 0
		n = len(nums)
		while j < n:
			if len(max_vals) == 0:
				max_vals.append(nums[j])
			else:
				while len(max_vals) != 0 and max_vals[-1] < nums[j]:
					max_vals.pop(-1)
				max_vals.append(nums[j])
			if j - i + 1 < k:
				j = j + 1
			elif j - i + 1:
				ans.append(max_vals[0])
				if nums[i] == max_vals[0]:
					max_vals.pop(0)
				i = i + 1
				j = j + 1
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		A = arr
		list1 = deque()
		ans = []
		l = r = 0
		while r < len(A):
			while list1 and list1[-1] < A[r]:
				list1.pop()
			list1.append(A[r])
			if r - l + 1 < k:
				r += 1
			elif r - l + 1 == k:
				ans.append(list1[0])
				if list1[0] == A[l]:
					list1.popleft()
				l += 1
				r += 1
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		max_val = max(arr[0:k])
		q = [max_val]
		for i in range(k, n):
			if arr[i - k] == max_val:
				max_val = max(arr[i - k + 1:i + 1])
			else:
				max_val = max(max_val, arr[i])
			q.append(max_val)
		return q


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		max_val = max(arr[0:k])
		res = [max_val]
		for i in range(k, n):
			if arr[i - k] == max_val:
				max_val = max(arr[i - k + 1:i + 1])
			else:
				max_val = max(max_val, arr[i])
			res.append(max_val)
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		from collections import deque
		n = len(arr)
		i = 0
		j = 0
		l = []
		ans = []
		while j < n:
			l.append(arr[j])
			if len(l) > 1 and l[-1] > l[-2]:
				while len(l) > 1 and l[-1] > l[-2]:
					l.pop(-2)
			if j - i + 1 < k:
				j = j + 1
			elif j - i + 1 == k:
				ans.append(l[0])
				if arr[i] == l[0]:
					l.pop(0)
				i = i + 1
				j = j + 1
		return ans
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		i = j = 0
		queue = []
		arr1 = []
		while j < n:
			while len(queue) > 0 and arr[j] > queue[-1]:
				queue.pop()
			queue.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				arr1.append(queue[0])
				if queue[0] == arr[i]:
					queue.pop(0)
				i += 1
				j += 1
		return arr1


from collections import deque

class Solution:

	def max_of_subarrays(self, A, n, B):
		ans = []
		lst = deque()
		(i, j) = (0, 0)
		while j < len(A):
			while len(lst) > 0:
				if A[j] > lst[-1]:
					lst.pop()
				else:
					break
			lst.append(A[j])
			if j - i + 1 < B:
				j += 1
			elif j - i + 1 == B:
				ans.append(lst[0])
				if lst[0] == A[i]:
					lst.popleft()
				i += 1
				j += 1
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, N, K):
		result = []
		dq = deque()
		for i in range(K):
			while dq and arr[i] >= arr[dq[-1]]:
				dq.pop()
			dq.append(i)
		for i in range(K, N):
			result.append(arr[dq[0]])
			while dq and dq[0] <= i - K:
				dq.popleft()
			while dq and arr[i] >= arr[dq[-1]]:
				dq.pop()
			dq.append(i)
		result.append(arr[dq[0]])
		return result


class Solution:

	def max_of_subarrays(self, arr, n, k):
		import collections
		from collections import deque
		q = collections.deque()
		l = r = 0
		fin = []
		while r < len(arr):
			while q and arr[q[-1]] < arr[r]:
				q.pop()
			q.append(r)
			if l > q[0]:
				q.popleft()
			if r + 1 >= k:
				fin.append(arr[q[0]])
				l += 1
			r += 1
		return fin


import heapq as h

class Solution:

	def max_of_subarrays(self, arr, n, k):
		l = []
		h.heapify(l)
		maxi = -10 ** 9
		j = 0
		l1 = []
		for i in range(n):
			h.heappush(l, [-arr[i], i])
			if i - j + 1 == k:
				while l[0][1] < j:
					h.heappop(l)
				l1.append(-l[0][0])
				j = j + 1
		return l1


class Solution:

	def max_of_subarrays(self, arr, N, K):
		from collections import deque
		Qi = deque()
		ans = []
		for i in range(K):
			while Qi and arr[i] >= arr[Qi[-1]]:
				Qi.pop()
			Qi.append(i)
		for i in range(K, N):
			ans.append(str(arr[Qi[0]]))
			while Qi and Qi[0] <= i - K:
				Qi.popleft()
			while Qi and arr[i] >= arr[Qi[-1]]:
				Qi.pop()
			Qi.append(i)
		ans.append(str(arr[Qi[0]]))
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		N = n
		K = k
		Qi = deque()
		ans = []
		for i in range(K):
			while Qi and arr[i] >= arr[Qi[-1]]:
				Qi.pop()
			Qi.append(i)
		for i in range(K, N):
			ans.append(arr[Qi[0]])
			while Qi and Qi[0] <= i - K:
				Qi.popleft()
			while Qi and arr[i] >= arr[Qi[-1]]:
				Qi.pop()
			Qi.append(i)
		ans.append(arr[Qi[0]])
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		nums = arr
		mem = deque()
		output = []
		(l, r) = (0, 0)
		while r < len(nums):
			while mem and nums[mem[-1]] < nums[r]:
				mem.pop()
			mem.append(r)
			if l > mem[0]:
				mem.popleft()
			if r + 1 >= k:
				output.append(nums[mem[0]])
				l += 1
			r += 1
		return output
		output = []
		stack = deque()
		for (i, j) in enumerate(arr):
			while len(stack) != 0 and arr[stack[-1]] < j:
				stack.pop()
			stack.append(i)
			if stack[0] < i - k + 1:
				stack.popleft()
			if i >= k - 1:
				output.append(arr[stack[0]])
		return output


import collections

class Solution:

	def max_of_subarrays(self, a, n, k):
		q = collections.deque()
		l = 0
		res = []
		for i in range(len(a)):
			while q and a[q[-1]] < a[i]:
				q.pop()
			q.append(i)
			if i + 1 >= k:
				res.append(a[q[0]])
				l += 1
			if l > q[0]:
				q.popleft()
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		result = []
		lis = []
		i = 0
		j = 0
		while j < n:
			while len(result) != 0 and arr[j] > result[-1]:
				result.pop(-1)
			result.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				lis.append(result[0])
				if result[0] == arr[i]:
					result.pop(0)
				i += 1
				j += 1
		return lis


import math

class Solution:

	def max_of_subarrays(self, arr, n, k):
		stack = []
		maximum = -math.inf
		for i in range(k):
			if arr[i] > maximum:
				maximum = arr[i]
		stack.append(maximum)
		j = 0
		for i in range(1, n - k + 1):
			if arr[i + k - 1] >= maximum:
				maximum = arr[i + k - 1]
				stack.append(maximum)
			elif arr[j] == maximum:
				maximum = max(arr[i:i + k])
				stack.append(maximum)
			else:
				stack.append(maximum)
			j += 1
		return stack


from collections import deque
import heapq

class Solution:

	def helper(self, n, l1, k):
		hq = []
		heapq.heapify(hq)
		for i in range(k - 1):
			heapq.heappush(hq, [-l1[i], i])
		j = 0
		res = []
		for i in range(k - 1, n):
			heapq.heappush(hq, [-l1[i], i])
			while hq:
				root = hq[0]
				val = -root[0]
				idx = root[1]
				if idx >= i + 1 - k:
					res.append(val)
					break
				else:
					heapq.heappop(hq)
		return res

	def max_of_subarrays(self, l1, n, k):
		return self.helper(n, l1, k)


class Solution:

	def max_of_subarrays(self, arr, n, k):
		l = []
		ma = max(arr[:k])
		pos = arr.index(ma)
		l.append(ma)
		for i in range(1, n - k + 1):
			if i <= pos:
				if ma < arr[i + k - 1]:
					ma = arr[i + k - 1]
					pos = i + k - 1
				l.append(ma)
			else:
				ma = max(arr[i:i + k])
				pos = i
				l.append(ma)
		return l


class Solution:

	def max_of_subarrays(self, arr, n, k):
		n = len(arr)
		max_val = max(arr[:k])
		res = [max_val]
		for i in range(k, n):
			if arr[i - k] == max_val:
				max_val = max(arr[i - k + 1:i + 1])
			else:
				max_val = max(max_val, arr[i])
			res.append(max_val)
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		l = []
		st = []
		(i, j) = (0, 0)
		while j < n:
			while st and st[-1] < arr[j]:
				st.pop(-1)
			st.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				l.append(st[0])
				if arr[i] == st[0]:
					st.pop(0)
				i += 1
				j += 1
		return l


class Solution:

	def max_of_subarrays(self, arr, n, k):
		output = []
		(l, r) = (0, 0)
		q = deque()
		while r < len(arr):
			while q and arr[q[-1]] <= arr[r]:
				q.pop()
			q.append(r)
			if l > q[0]:
				q.popleft()
			if r + 1 >= k:
				output.append(arr[q[0]])
				l += 1
			r += 1
		return output


class Solution:

	def max_of_subarrays(self, arr, n, k):
		q = deque()
		n = len(arr)
		(i, j) = (0, 0)
		res = []
		temp = []
		while j < n:
			while q and arr[j] > q[-1]:
				q.pop()
			q.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				res.append(q[0])
				if q[0] == arr[i]:
					q.popleft()
				i += 1
				j += 1
		return res


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		d = deque()
		ans = []
		for i in range(n):
			while len(d) > 0 and arr[d[-1]] < arr[i]:
				d.pop()
			d.append(i)
			if i - d[0] >= k:
				d.popleft()
			if i >= k - 1:
				ans.append(arr[d[0]])
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		i = 0
		j = 0
		li = []
		ans = []
		heap = []
		while j < n:
			if j - i + 1 < k:
				while li and li[-1] < arr[j]:
					li.pop()
				else:
					li.append(arr[j])
				j += 1
			elif j - i + 1 == k:
				while li and li[-1] < arr[j]:
					li.pop()
				else:
					li.append(arr[j])
				if arr[i] == li[0]:
					ans.append(li.pop(0))
				else:
					ans.append(li[0])
				i += 1
				j += 1
		return ans


class Solution:

	def max_of_subarrays(self, arr, n, k):
		l = []
		i = 0
		j = 0
		ans = []
		while i < n:
			while len(l) > 0 and l[-1] < arr[i]:
				l.pop()
			l.append(arr[i])
			if i - j + 1 == k:
				ans.append(l[0])
				if l[0] == arr[j]:
					l.pop(0)
				i = i + 1
				j = j + 1
			else:
				i = i + 1
		return ans