Given an integer array. The task is to find the maximum of the minimum of every window size in the array.
Note: Window size varies from 1 to the size of the Array.
Example 1:
Input:
N = 7
arr[] = {10,20,30,50,10,70,30}
Output: 70 30 20 10 10 10 10 
Explanation: 
1.First element in output
indicates maximum of minimums of all
windows of size 1.
2.Minimums of windows of size 1 are {10},
 {20}, {30}, {50},{10}, {70} and {30}. 
 Maximum of these minimums is 70. 
3. Second element in output indicates
maximum of minimums of all windows of
size 2. 
4. Minimums of windows of size 2
are {10}, {20}, {30}, {10}, {10}, and
{30}.
5. Maximum of these minimums is 30 
Third element in output indicates
maximum of minimums of all windows of
size 3. 
6. Minimums of windows of size 3
are {10}, {20}, {10}, {10} and {10}.
7.Maximum of these minimums is 20. 
Similarly other elements of output are
computed.
Example 2:
Input:
N = 3
arr[] = {10,20,30}
Output: 30 20 10
Explanation: First element in output
indicates maximum of minimums of all
windows of size 1.Minimums of windows
of size 1 are {10} , {20} , {30}.
Maximum of these minimums are 30 and
similarly other outputs can be computed
Your Task:
The task is to complete the function maxOfMin() which takes the array arr[] and its size N as inputs and finds the maximum of minimum of every window size and returns an array containing the result. 
Expected Time Complxity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3

class Solution:
    
    #Function to find maximum of minimums of every window size.
    def maxOfMin(self,arr,n):
    # code here

Solutions:
class Solution:

	def maxOfMin(self, arr, n):
		stack = []
		left = [-1] * n
		right = [n] * n
		for i in range(n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				left[i] = stack[-1]
			stack.append(i)
		stack.clear()
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] > arr[i]:
				stack.pop()
			if stack:
				right[i] = stack[-1]
			stack.append(i)
		result = [0] * (n + 1)
		for i in range(n):
			window_size = right[i] - left[i] - 1
			result[window_size] = max(result[window_size], arr[i])
		for i in range(n - 1, 0, -1):
			result[i] = max(result[i], result[i + 1])
		return result[1:]


class Solution:

	def maxOfMin(self, arr, n):
		s = []
		left = [-1] * (n + 1)
		right = [n] * (n + 1)
		for i in range(n):
			while len(s) != 0 and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				left[i] = s[-1]
			s.append(i)
		s = []
		for i in range(n - 1, -1, -1):
			while len(s) != 0 and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				right[i] = s[-1]
			s.append(i)
		res = [0] * (n + 1)
		for i in range(n):
			L = right[i] - left[i] - 1
			res[L] = max(res[L], arr[i])
		for i in range(n - 1, 0, -1):
			res[i] = max(res[i], res[i + 1])
		return res[1:]


class Solution:

	def maxOfMin(self, arr, n):
		arr1 = [0 for i in range(n)]
		arr2 = [0 for i in range(n)]
		stk = []
		for i in range(n):
			if len(stk) == 0:
				arr1[i] = -1
			else:
				while len(stk) > 0 and arr[stk[-1]] >= arr[i]:
					stk.pop()
				if len(stk) == 0:
					arr1[i] = -1
				else:
					arr1[i] = stk[-1]
			stk.append(i)
		stk = []
		for i in range(n - 1, -1, -1):
			if len(stk) == 0:
				arr2[i] = n
			else:
				while len(stk) > 0 and arr[stk[-1]] >= arr[i]:
					stk.pop()
				if len(stk) == 0:
					arr2[i] = n
				else:
					arr2[i] = stk[-1]
			stk.append(i)
		ans = [0 for i in range(n + 1)]
		for i in range(n):
			ln = arr2[i] - arr1[i] - 1
			ans[ln] = max(ans[ln], arr[i])
		for i in range(n - 1, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:n + 1]


class Solution:

	def maxOfMin(self, arr, n):
		(st, left, right, ans) = ([], [-1] * (n + 1), [n] * (n + 1), [0] * (n + 1))
		for i in range(n):
			while st and arr[st[-1]] >= arr[i]:
				st.pop()
			if st:
				left[i] = st[-1]
			st.append(i)
		while st:
			st.pop()
		for i in range(n - 1, -1, -1):
			while st and arr[st[-1]] >= arr[i]:
				st.pop()
			if st:
				right[i] = st[-1]
			st.append(i)
		for i in range(n):
			Len = right[i] - left[i] - 1
			ans[Len] = max(ans[Len], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


class Solution:

	def maxOfMin(self, arr, n):
		stack = []
		r = [n for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				r[i] = stack[-1]
			stack.append(i)
		stack = []
		l = [-1 for i in range(n + 1)]
		for i in range(n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				l[i] = stack[-1]
			stack.append(i)
		ans = [0 for i in range(n + 1)]
		for i in range(n):
			len = r[i] - l[i] - 1
			ans[len] = max(ans[len], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		res = [ans[i] for i in range(1, n + 1)]
		return res


import collections

class Solution:

	def maxOfMin(self, arr, n):
		s = []
		left = [-1] * n
		right = [n] * n
		for i in range(n):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if s:
				left[i] = s[-1]
			s.append(i)
		while s:
			s.pop()
		for i in range(n - 1, -1, -1):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if s:
				right[i] = s[-1]
			s.append(i)
		ans = [0] * (n + 1)
		for i in range(n):
			lenght = right[i] - left[i] - 1
			ans[lenght] = max(ans[lenght], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:n + 1]


class Solution:

	def maxOfMin(self, arr, n):
		res = [0] * (n + 1)
		for k in range(1, n + 1):
			maxOfMin = float('-inf')
			for i in range(n - k + 1):
				mini = arr[i]
				for j in range(k):
					if arr[i + j] < mini:
						mini = arr[i + j]
				if mini > maxOfMin:
					maxOfMin = mini
			res[k] = maxOfMin
		return res[1:]

	def maxOfMin(self, arr, n):
		s = []
		left = [-1] * (n + 1)
		right = [n] * (n + 1)
		for i in range(n):
			while len(s) and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s):
				left[i] = s[-1]
			s.append(i)
		while len(s):
			s.pop()
		for i in range(n - 1, -1, -1):
			while len(s) and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s):
				right[i] = s[-1]
			s.append(i)
		res = [0] * (n + 1)
		for i in range(n + 1):
			res[i] = 0
		for i in range(n):
			Len = right[i] - left[i] - 1
			res[Len] = max(res[Len], arr[i])
		for i in range(n - 1, 0, -1):
			res[i] = max(res[i], res[i + 1])
		return res[1:]


class Solution:

	def maxOfMin(self, arr, n):
		res = [0 for i in range(n + 1)]
		st = []
		for i in range(n + 1):
			while st and (i == n or arr[st[-1]] > arr[i]):
				cur = st.pop()
				l = i - st[-1] - 1 if st else i
				res[l] = max(res[l], arr[cur])
			st.append(i)
		for i in range(n - 1, -1, -1):
			res[i] = max(res[i + 1], res[i])
		return res[1:]


class Solution:

	def maxOfMin(self, a, n):
		stack = []
		left = [-1 for i in range(n)]
		right = [n for i in range(n)]
		for i in range(n):
			while len(stack) and a[stack[-1]] >= a[i]:
				stack.pop()
			if len(stack):
				left[i] = stack[-1]
			stack.append(i)
		stack = []
		for i in range(n - 1, -1, -1):
			while len(stack) and a[stack[-1]] >= a[i]:
				stack.pop()
			if len(stack):
				right[i] = stack[-1]
			stack.append(i)
		ans = [0 for i in range(n + 1)]
		for i in range(n):
			length = right[i] - left[i] - 1
			ans[length] = max(ans[length], a[i])
		for i in range(n - 1, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


class Solution:

	def maxOfMin(self, arr, n):
		nextsmallarr = self.nextSmaller(arr)
		prevsmallarr = self.prevSmaller(arr)
		ans = [0] * n
		for i in range(n):
			windowSize = nextsmallarr[i] - prevsmallarr[i] - 1
			ans[windowSize - 1] = max(arr[i], ans[windowSize - 1])
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans

	def nextSmaller(self, a):
		stack = [len(a) - 1]
		ans = []
		for i in range(len(a) - 1, -1, -1):
			while stack and a[stack[-1]] >= a[i]:
				stack.pop()
			if not stack:
				ans.append(len(a))
			else:
				ans.append(stack[-1])
			stack.append(i)
		return ans[::-1]

	def prevSmaller(self, a):
		stack = [0]
		ans = []
		for i in range(len(a)):
			while stack and a[stack[-1]] >= a[i]:
				stack.pop()
			if not stack:
				ans.append(-1)
			else:
				ans.append(stack[-1])
			stack.append(i)
		return ans


class Solution:

	def maxOfMin(self, arr, n):
		mi = min(arr)
		has = [0] * n
		has[n - 1] = mi
		pos = [0] * n
		stack = []
		for i in range(0, n):
			if len(stack) and stack[len(stack) - 1][0] > arr[i]:
				while len(stack) > 0 and stack[len(stack) - 1][0] > arr[i]:
					t = stack.pop()
					pos[t[1]] = i - t[1] - 1
			stack.append([arr[i], i])
		while stack:
			t = stack.pop()
			pos[t[1]] = n - t[1] - 1
		stack = []
		for i in range(n - 1, -1, -1):
			if len(stack) and stack[len(stack) - 1][0] > arr[i]:
				while len(stack) > 0 and stack[len(stack) - 1][0] > arr[i]:
					t = stack.pop()
					pos[t[1]] += t[1] - i - 1
			stack.append([arr[i], i])
		while stack:
			t = stack.pop()
			pos[t[1]] += t[1]
		for i in range(0, n):
			if arr[i] > has[pos[i]]:
				has[pos[i]] = arr[i]
		for i in range(n - 1, 0, -1):
			if has[i - 1] <= has[i]:
				has[i - 1] = has[i]
		return has


class Solution:

	def maxOfMin(self, arr, n):
		q = []
		left = [-1] * n
		right = [n] * n
		for i in range(n):
			while q and arr[q[-1]] >= arr[i]:
				q.pop()
			if q:
				left[i] = q[-1]
			q.append(i)
		q = []
		for i in range(n):
			while q and arr[q[-1]] > arr[i]:
				idx = q.pop()
				right[idx] = i
			q.append(i)
		del q
		ans = [0] * n
		for i in range(n):
			length = right[i] - left[i] - 1
			ans[length - 1] = max(ans[length - 1], arr[i])
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def maxOfMin(self, arr, n):

		def nextSmallerLeft(arr, n):
			left = [-1 for i in range(n)]
			stack = []
			for i in range(n - 1, -1, -1):
				while len(stack) != 0 and arr[i] < arr[stack[-1]]:
					popped = stack.pop()
					left[popped] = i
				stack.append(i)
			return left

		def nextSmallerRight(arr, n):
			right = [n for i in range(n)]
			stack = []
			for i in range(n):
				while len(stack) != 0 and arr[i] < arr[stack[-1]]:
					popped = stack.pop()
					right[popped] = i
				stack.append(i)
			return right
		left = nextSmallerLeft(arr, n)
		right = nextSmallerRight(arr, n)
		output = [0 for i in range(n + 1)]
		for i in range(n):
			length = right[i] - left[i] - 1
			output[length] = max(output[length], arr[i])
		for i in range(n - 1, 0, -1):
			output[i] = max(output[i + 1], output[i])
		return output[1:]


class Solution:

	def maxOfMin(self, arr, n):
		left = [0] * (n + 1)
		right = [0] * (n + 1)
		stack = []
		for i in range(n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if not stack:
				left[i] = -1
			else:
				left[i] = stack[-1]
			stack.append(i)
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if not stack:
				right[i] = n
			else:
				right[i] = stack[-1]
			stack.append(i)
		ans = [0] * (n + 1)
		for i in range(n):
			len_subarr = right[i] - left[i] - 1
			ans[len_subarr] = max(ans[len_subarr], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


class Solution:

	def maxOfMin(self, arr, n):
		stack = [0]
		res = [-1] * (n + 1)
		for i in range(1, n):
			while stack and arr[stack[-1]] >= arr[i]:
				tp = stack.pop()
				w_size = i if not stack else i - stack[-1] - 1
				res[w_size] = max(res[w_size], arr[tp])
			stack.append(i)
		while stack:
			tp = stack.pop()
			w_size = n if not stack else n - stack[-1] - 1
			res[w_size] = max(res[w_size], arr[tp])
		for i in range(n - 1, -1, -1):
			res[i] = max(res[i], res[i + 1])
		return res[1:]


def nextSmallerElement(A):
	n = len(A)
	nse = [n] * n
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and A[stack[-1]] >= A[i]:
			stack.pop()
		if stack:
			nse[i] = stack[-1]
		stack.append(i)
	return nse

class Solution:

	def maxOfMin(self, A, n):
		nse = nextSmallerElement(A)
		lse = nextSmallerElement(A[::-1])[::-1]
		lse = [n - i - 1 for i in lse]
		ans = [-10 ** 9] * n
		for i in range(n):
			ln = nse[i] - lse[i] - 2
			ans[ln] = max(ans[ln], A[i])
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


def prevSmaller(arr):
	res = list()
	stack = list()
	for i in range(len(arr)):
		while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
			stack.pop()
		if len(stack) == 0:
			res.append(-1)
		else:
			res.append(stack[-1])
		stack.append(i)
	return res

def nextSmaller(arr):
	res = [0] * len(arr)
	stack = list()
	for i in range(len(arr) - 1, -1, -1):
		while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
			stack.pop()
		if len(stack) == 0:
			res[i] = -1
		else:
			res[i] = stack[-1]
		stack.append(i)
	return res

class Solution:

	def maxOfMin(self, arr, n):
		prev = prevSmaller(arr)
		next = nextSmaller(arr)
		ans = [0] * (n + 1)
		for i in range(n):
			length = next[i] - prev[i] - 1
			ans[length] = max(ans[length], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


def get_next_greater(arr, n):
	res = [len(arr)]
	stack = [n - 1]
	for i in range(n - 2, -1, -1):
		while len(stack) > 0 and arr[i] <= arr[stack[-1]]:
			stack.pop()
		if len(stack) == 0:
			res.append(len(arr))
		else:
			res.append(stack[-1])
		stack.append(i)
	return res[::-1]

def get_prev_greater(arr, n):
	res = [-1]
	stack = [0]
	for i in range(1, n):
		while len(stack) > 0 and arr[i] <= arr[stack[-1]]:
			stack.pop()
		if len(stack) == 0:
			res.append(-1)
		else:
			res.append(stack[-1])
		stack.append(i)
	return res

class Solution:

	def maxOfMin(self, arr, n):
		ans = [0] * (n + 1)
		nxs = get_next_greater(arr, n)
		pvs = get_prev_greater(arr, n)
		for i in range(n):
			len = nxs[i] - pvs[i] - 1
			ans[len] = max(ans[len], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


class Solution:

	def maxOfMin(self, arr, n):
		ple = [-1 for _ in range(n)]
		stack = []
		for idx in range(len(arr)):
			while stack and arr[stack[-1]] >= arr[idx]:
				stack.pop()
			if stack:
				ple[idx] = stack[-1]
			stack.append(idx)
		nle = [n for _ in range(n)]
		stack = []
		for idx in reversed(range(len(arr))):
			while stack and arr[stack[-1]] >= arr[idx]:
				stack.pop()
			if stack:
				nle[idx] = stack[-1]
			stack.append(idx)
		res = [0 for _ in range(n)]
		for idx in range(n):
			diff = nle[idx] - ple[idx] - 1
			res[diff - 1] = max(res[diff - 1], arr[idx])
		for idx in reversed(range(n - 1)):
			res[idx] = max(res[idx], res[idx + 1])
		return res


class Solution:

	def maxOfMin(self, arr, n):
		s = []
		left = [-1] * n
		right = [n] * n
		for i in range(n):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				left[i] = s[-1]
			s.append(i)
		s = []
		for i in range(n - 1, -1, -1):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				right[i] = s[-1]
			s.append(i)
		maxAns = [0] * n
		for i in range(n):
			Len = right[i] - left[i] - 2
			maxAns[Len] = max(maxAns[Len], arr[i])
		for i in range(n - 2, -1, -1):
			maxAns[i] = max(maxAns[i], maxAns[i + 1])
		return maxAns


class Solution:

	def maxOfMin(self, a, n):
		ls = [-1] * n
		rs = [n] * n
		stack = []
		for i in range(n):
			while stack and a[stack[-1]] > a[i]:
				rs[stack.pop()] = i
			stack.append(i)
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and a[stack[-1]] > a[i]:
				ls[stack.pop()] = i
			stack.append(i)
		ans = [0] * (n + 1)
		for i in range(n):
			subL = rs[i] - ls[i] - 1
			ans[subL] = max(ans[subL], a[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


class Solution:

	def maxOfMin(self, arr, n):
		ans = [0 for _ in range(len(arr))]
		stack = []
		left = [-1 for i in range(len(arr))]
		right = [len(arr) for i in range(len(arr))]
		for i in range(n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack != []:
				left[i] = stack[-1]
			stack.append(i)
		stack.clear()
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack != []:
				right[i] = stack[-1]
			stack.append(i)
		for i in range(len(arr)):
			leng = right[i] - left[i] - 1
			ans[leng - 1] = max(ans[leng - 1], arr[i])
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def beforeLesserElement(self, arr, n):
		s = []
		res = [0] * n
		for i in range(n):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if s == []:
				res[i] = -1
			else:
				res[i] = s[-1]
			s.append(i)
		return res

	def nextLesserElement(self, arr, n):
		s = []
		res = [0] * n
		for i in range(n - 1, -1, -1):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if s == []:
				res[i] = n
			else:
				res[i] = s[-1]
			s.append(i)
		return res

	def maxOfMin(self, arr, n):
		before = self.beforeLesserElement(arr, n)
		nextt = self.nextLesserElement(arr, n)
		res = [0] * (n + 1)
		for i in range(n):
			l = nextt[i] - before[i] - 1
			res[l] = max(res[l], arr[i])
		for i in range(n - 1, 0, -1):
			res[i] = max(res[i], res[i + 1])
		return res[1:]


from collections import deque

class Solution:

	def slidingWindow(self, nums, k):

	def maxOfMin(self, arr, n):
		s = []
		left = [-1] * (n + 1)
		right = [n] * (n + 1)
		for i in range(n):
			while len(s) != 0 and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				left[i] = s[-1]
			s.append(i)
		s.clear()
		for i in range(n - 1, -1, -1):
			while len(s) != 0 and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				right[i] = s[-1]
			s.append(i)
		ans = [0] * (n + 1)
		for i in range(n):
			Len = right[i] - left[i] - 1
			ans[Len] = max(ans[Len], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		ans.pop(0)
		return ans


class Solution:

	def maxOfMin(self, arr, n):
		right_min = [n] * n
		stack = []
		for (i, num) in enumerate(arr):
			while stack and arr[stack[-1]] > num:
				prev_idx = stack.pop()
				right_min[prev_idx] = i
			stack.append(i)
		left_min = [-1] * n
		for i in range(n - 1, -1, -1):
			num = arr[i]
			while stack and arr[stack[-1]] > num:
				prev_idx = stack.pop()
				left_min[prev_idx] = i
			stack.append(i)
		ans = [float('-inf')] * (n + 1)
		for i in range(n):
			length = right_min[i] - left_min[i] - 1
			ans[length] = max(ans[length], arr[i])
		for i in range(n - 1, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


class Solution:

	def maxOfMin(self, arr, n):
		l_small = [-1] * n
		r_small = [n] * n
		stack = []
		for i in range(n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if len(stack) != 0:
				l_small[i] = stack[-1]
			stack.append(i)
		stack.clear()
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if len(stack) != 0:
				r_small[i] = stack[-1]
			stack.append(i)
		ans = [0] * (n + 1)
		for i in range(n):
			pres_res = r_small[i] - l_small[i] - 1
			ans[pres_res] = max(ans[pres_res], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i + 1], ans[i])
		return ans[1:n + 2]


class Solution:

	def maxOfMin(self, arr, n):
		left = [0] * n
		right = [0] * n
		ans = [float('-inf')] * n
		stack = []
		for i in range(n):
			while stack != [] and stack[-1][0] >= arr[i]:
				stack.pop()
			if stack == []:
				left[i] = -1
			else:
				left[i] = stack[-1][1]
			stack.append((arr[i], i))
		stack = []
		for i in range(n - 1, -1, -1):
			while stack != [] and stack[-1][0] >= arr[i]:
				stack.pop()
			if stack == []:
				right[i] = n
			else:
				right[i] = stack[-1][1]
			stack.append((arr[i], i))
		for i in range(n):
			length = right[i] - left[i] - 1
			if arr[i] > ans[length - 1]:
				ans[length - 1] = arr[i]
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def maxOfMin(self, arr, n):

		def nse(arr):
			n = len(arr)
			stk = []
			ans = [n] * n
			for i in range(n):
				while stk and arr[stk[-1]] > arr[i]:
					ans[stk.pop()] = i
				stk.append(i)
			return ans

		def pse(arr):
			n = len(arr)
			stk = []
			ans = [-1] * n
			for i in range(n - 1, -1, -1):
				while stk and arr[stk[-1]] > arr[i]:
					ans[stk.pop()] = i
				stk.append(i)
			return ans
		ns = nse(arr)
		ps = pse(arr)
		ans = [float('-inf')] * n
		for i in range(n):
			l = ns[i] - ps[i] - 1
			ans[l - 1] = max(ans[l - 1], arr[i])
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def maxOfMin(self, arr, n):

		def ns(A):
			n = len(A)
			ans = [n] * n
			s = []
			for i in range(n):
				if len(s) and A[i] < A[s[-1]]:
					while len(s) and A[i] < A[s[-1]]:
						ans[s.pop()] = i
				s.append(i)
			return ans

		def ps(A):
			n = len(A)
			ans = [-1] * n
			s = []
			for i in range(n - 1, -1, -1):
				if len(s) and A[i] < A[s[-1]]:
					while len(s) and A[i] < A[s[-1]]:
						ans[s.pop()] = i
				s.append(i)
			return ans
		nx = ns(arr)
		p = ps(arr)
		ans = [0] * (n + 1)
		for i in range(n):
			ln = nx[i] - p[i] - 1
			ans[ln] = max(ans[ln], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


from collections import deque

class Solution:

	def NS(self, arr, l=None, r=None):
		n = len(arr)
		if r:
			(a, b, c, ps) = (n - 1, -1, -1, n)
		else:
			(a, b, c, ps) = (0, n, 1, -1)
		ind = [ps] * n
		stack = deque()
		for i in range(a, b, c):
			if stack and arr[i] > stack[-1][0]:
				ind[i] = stack[-1][1]
			else:
				while stack and arr[i] <= stack[-1][0]:
					stack.pop()
				if stack:
					ind[i] = stack[-1][1]
			stack.append([arr[i], i])
		return ind

	def maxOfMin(self, arr, n):
		NSR = self.NS(arr, False, True)
		NSL = self.NS(arr, True, False)
		wid = [-1] * n
		for i in range(n):
			wid[i] = NSR[i] - NSL[i] - 1
		d = dict()
		for i in range(n):
			if wid[i] not in d:
				d[wid[i]] = arr[i]
			elif arr[i] > d[wid[i]]:
				d[wid[i]] = arr[i]
		ans = [-1] * n
		for k in sorted(d):
			ans[k - 1] = d[k]
		ans[-1] = min(arr)
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def maxOfMin(self, array, n):
		left = [-1] * n
		right = [n] * n
		stack1 = list()
		stack2 = list()
		for i in range(n):
			while stack1 and array[stack1[-1]] >= array[i]:
				stack1.pop()
			if stack1:
				left[i] = stack1[-1]
			stack1.append(i)
		for i in range(n - 1, -1, -1):
			while stack2 and array[stack2[-1]] >= array[i]:
				stack2.pop()
			if stack2:
				right[i] = stack2[-1]
			stack2.append(i)
		len_ = [0] * n
		for i in range(n):
			len_[right[i] - left[i] - 2] = max(len_[right[i] - left[i] - 2], array[i])
		for i in range(n - 2, -1, -1):
			len_[i] = max(len_[i], len_[i + 1])
		return len_


class Solution:

	def maxOfMin(self, arr, n):
		larr = [-1] * n
		rarr = [n] * n
		st = []
		for i in range(0, n):
			if len(st) == 0:
				st.append(i)
			elif arr[st[-1]] < arr[i]:
				larr[i] = st[-1]
				st.append(i)
			else:
				while len(st) > 0 and arr[st[-1]] >= arr[i]:
					st.pop()
				if len(st) > 0:
					larr[i] = st[-1]
				st.append(i)
		st = []
		for i in range(n - 1, -1, -1):
			if len(st) == 0:
				st.append(i)
			elif arr[st[-1]] < arr[i]:
				rarr[i] = st[-1]
				st.append(i)
			else:
				while len(st) > 0 and arr[st[-1]] >= arr[i]:
					st.pop()
				if len(st) > 0:
					rarr[i] = st[-1]
				st.append(i)
		res = [-9999] * (n + 1)
		x = []
		for i in range(n):
			diff = rarr[i] - larr[i] - 1
			res[diff] = max(res[diff], arr[i])
		x = res[n]
		for i in range(n - 1, 0, -1):
			if res[i] < x:
				res[i] = x
			else:
				x = res[i]
		return res[1:]


class Solution:

	def nextSmaller(self, arr):
		ns = [None] * len(arr)
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			ns[i] = len(arr) if len(stack) == 0 else stack[-1]
			stack.append(i)
		return ns

	def prevSmaller(self, arr):
		ps = [None] * len(arr)
		stack = []
		for i in range(len(arr)):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			ps[i] = -1 if len(stack) == 0 else stack[-1]
			stack.append(i)
		return ps

	def maxOfMin(self, arr, n):
		ns = self.nextSmaller(arr)
		ps = self.prevSmaller(arr)
		result = [0] * n
		for i in range(n):
			size = ns[i] - ps[i] - 1
			result[size - 1] = max(result[size - 1], arr[i])
		for i in range(n - 2, -1, -1):
			result[i] = max(result[i], result[i + 1])
		return result


class Solution:

	def maxOfMin(self, histogram, n):
		prev_ele = []
		new_ele = []
		stack = []
		for i in range(len(histogram)):
			while stack and histogram[stack[-1]] >= histogram[i]:
				stack.pop()
			if not stack:
				prev_ele.append(-1)
			if stack:
				prev_ele.append(stack[-1])
			stack.append(i)
		stack = []
		for i in range(len(histogram) - 1, -1, -1):
			while stack and histogram[stack[-1]] >= histogram[i]:
				stack.pop()
			if not stack:
				new_ele.append(len(histogram))
			if stack:
				new_ele.append(stack[-1])
			stack.append(i)
		new_ele = new_ele[::-1]
		check_arr = {}
		for i in range(n):
			if check_arr.get(new_ele[i] - prev_ele[i] - 1) == None:
				check_arr[new_ele[i] - prev_ele[i] - 1] = histogram[i]
			elif check_arr[new_ele[i] - prev_ele[i] - 1] < histogram[i]:
				check_arr[new_ele[i] - prev_ele[i] - 1] = histogram[i]
		op = []
		for i in range(n, 0, -1):
			if check_arr.get(i) == None:
				op.append(val)
			elif i == n:
				val = check_arr[i]
				op.append(val)
			elif val > check_arr[i]:
				op.append(val)
			else:
				op.append(check_arr[i])
				val = check_arr[i]
		return op[::-1]


class Solution:

	def maxOfMin(self, arr, n):

		def next_smaller(arr, n):
			res = []
			stack = []
			for i in range(n - 1, -1, -1):
				while stack and arr[stack[-1]] >= arr[i]:
					stack.pop()
				if stack:
					res.append(stack[-1])
				else:
					res.append(n)
				stack.append(i)
			return res[::-1]

		def previous_smaller(arr, n):
			res = []
			stack = []
			for i in range(n):
				while stack and arr[stack[-1]] >= arr[i]:
					stack.pop()
				if stack:
					res.append(stack[-1])
				else:
					res.append(-1)
				stack.append(i)
			return res
		left = previous_smaller(arr, n)
		right = next_smaller(arr, n)
		ans = [0] * (n + 1)
		for i in range(n):
			length = right[i] - left[i] - 1
			ans[length] = max(ans[length], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:]


class Solution:

	def maxOfMin(self, arr, n):
		ns = [n] * len(arr)
		ps = [-1] * len(arr)
		ans = [-1] * len(arr)
		stack = []
		for (i, val) in enumerate(arr):
			while stack and stack[-1][1] >= val:
				(ind, value) = stack.pop()
				ns[ind] = i
			stack.append([i, val])
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			while stack and stack[-1][1] > arr[i]:
				ps[stack[-1][0]] = i
				stack.pop()
			stack.append([i, arr[i]])
		for i in range(len(arr)):
			try:
				ans[ns[i] - ps[i] - 2] = max(ans[ns[i] - ps[i] - 2], arr[i])
			except:
				print('asdf', ns[i] - ps[i] - 2, i)
		for i in range(len(ans) - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def maxOfMin(self, arr, n):
		s = []
		l = [-1 for i in range(n + 1)]
		r = [n for j in range(n + 1)]
		for i in range(n):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if s:
				l[i] = s[-1]
			s.append(i)
		while s:
			s.pop()
		for i in range(n - 1, -1, -1):
			while s and arr[s[-1]] >= arr[i]:
				s.pop()
			if s:
				r[i] = s[-1]
			s.append(i)
		ans = [0 for i in range(n + 1)]
		for i in range(n):
			x = r[i] - l[i] - 1
			ans[x] = max(ans[x], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		ans.pop(0)
		return ans


class Solution:

	def maxOfMin(self, arr, n):
		ans = [0] * n
		stack = []
		arr.append(0)
		for i in range(n + 1):
			while stack and arr[stack[-1]] >= arr[i]:
				idx = stack.pop()
				left = stack[-1] if stack else -1
				right = i
				window_size = right - left - 1
				ans[window_size - 1] = max(ans[window_size - 1], arr[idx])
			stack.append(i)
		for i in range(n - 2, -1, -1):
			if ans[i] == 0 or ans[i] < ans[i + 1]:
				ans[i] = ans[i + 1]
		return ans


from collections import deque

class Solution:

	def minSlidingWindow(self, nums, k):
		if k == len(nums):
			return [min(nums)]
		if k > len(nums):
			return None
		curr = deque([])
		res = []
		for i in range(len(nums)):
			if len(curr) > 0:
				if curr[0] == i - k:
					curr.popleft()
			while len(curr) > 0 and nums[curr[-1]] > nums[i]:
				curr.pop()
			curr.append(i)
			if i >= k - 1:
				res.append(nums[curr[0]])
		return res

	def maxOfMin(self, arr, n):
		s = []
		left = [-1] * (n + 1)
		right = [n] * (n + 1)
		for i in range(n):
			while len(s) != 0 and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				left[i] = s[-1]
			s.append(i)
		while len(s) != 0:
			s.pop()
		for i in range(n - 1, -1, -1):
			while len(s) != 0 and arr[s[-1]] >= arr[i]:
				s.pop()
			if len(s) != 0:
				right[i] = s[-1]
			s.append(i)
		ans = [0] * (n + 1)
		for i in range(n + 1):
			ans[i] = 0
		for i in range(n):
			Len = right[i] - left[i] - 1
			ans[Len] = max(ans[Len], arr[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans[1:n + 1]


import sys

class Solution:

	def prevSmaller(self, preMin, arr, n):
		stack = []
		for i in range(n):
			while len(stack) > 0 and arr[i] <= arr[stack[-1]]:
				stack.pop()
			preMin[i] = i + 1 if len(stack) == 0 else i - stack[-1]
			stack.append(i)
		return

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

	def maxOfMin(self, arr, n):
		preMin = [0] * n
		postMin = [0] * n
		ans = [-sys.maxsize] * n
		self.prevSmaller(preMin, arr, n)
		self.nextSmaller(postMin, arr, n)
		for i in range(n):
			postMin[i] += preMin[i] - 1
		for i in range(n):
			ans[postMin[i] - 1] = max(arr[i], ans[postMin[i] - 1])
		for i in range(n - 2, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def maxOfMin(self, arr, n):
		preMin = [0] * n
		postMin = [0] * n
		ans = [-float('INF')] * n
		stack = []
		for i in range(n):
			while len(stack) > 0 and arr[i] <= arr[stack[-1]]:
				stack.pop()
			preMin[i] = i + 1 if len(stack) == 0 else i - stack[-1]
			stack.append(i)
		while len(stack) > 0:
			stack.pop()
		for i in range(n - 1, -1, -1):
			while len(stack) > 0 and arr[i] <= arr[stack[-1]]:
				stack.pop()
			postMin[i] = n - i if len(stack) == 0 else stack[-1] - i
			stack.append(i)
		for i in range(n):
			postMin[i] += preMin[i] - 1
		for i in range(n):
			ans[postMin[i] - 1] = max(arr[i], ans[postMin[i] - 1])
		for i in range(n - 2, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


from collections import deque

class Solution:

	def maxOfMin(self, arr, n):
		left_small = [0] * n
		stack = []
		for i in range(n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				left_small[i] = stack[-1] + 1
			stack.append(i)
		right_small = [n - 1] * n
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				right_small[i] = stack[-1] - 1
			stack.append(i)
		windows = [0] * (n + 1)
		for i in range(n):
			window_len = right_small[i] - left_small[i] + 1
			if windows[window_len] < arr[i]:
				windows[window_len] = arr[i]
		for i in range(n - 1, -1, -1):
			windows[i] = max(windows[i + 1], windows[i])
		return windows[1:]


class Solution:

	def maxOfMin(self, arr, n):
		stack = []
		left = [-1] * n
		for i in range(n):
			while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if len(stack) != 0:
				left[i] = stack[-1]
			stack.append(i)
		stack = []
		right = [n] * n
		for i in range(n - 1, -1, -1):
			while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if len(stack) != 0:
				right[i] = stack[-1]
			stack.append(i)
		lens = [0] * (n + 1)
		for i in range(n):
			l = right[i] - left[i] - 1
			lens[l] = max(lens[l], arr[i])
		for i in range(n - 1, -1, -1):
			lens[i] = max(lens[i], lens[i + 1])
		return lens[1:]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maxOfMin(self, nums, n):
		next_smaller = [n] * n
		stack = []
		for i in range(n):
			while stack and nums[i] < nums[stack[-1]]:
				next_smaller[stack.pop()] = i
			stack.append(i)
		stack.clear()
		prev_smaller = [-1] * n
		for i in range(n - 1, -1, -1):
			while stack and nums[i] < nums[stack[-1]]:
				prev_smaller[stack.pop()] = i
			stack.append(i)
		res = [0] * n
		for i in range(n):
			l = prev_smaller[i] + 1
			r = next_smaller[i] - 1
			size = r - l + 1
			res[size - 1] = max(res[size - 1], nums[i])
		for i in range(n - 2, -1, -1):
			res[i] = max(res[i], res[i + 1])
		return res


class Solution:

	def maxOfMin(self, nums, n):
		next_smaller = [n] * n
		stack = []
		for i in range(n):
			while stack and nums[i] < nums[stack[-1]]:
				next_smaller[stack.pop()] = i
			stack.append(i)
		stack.clear()
		prev_smaller = [-1] * n
		for i in range(n - 1, -1, -1):
			while stack and nums[i] < nums[stack[-1]]:
				prev_smaller[stack.pop()] = i
			stack.append(i)
		res = [0] * n
		for i in range(n):
			l = prev_smaller[i] + 1
			r = next_smaller[i] - 1
			size = r - l + 1
			res[size - 1] = max(res[size - 1], nums[i])
		for i in range(n - 2, -1, -1):
			res[i] = max(res[i], res[i + 1])
		return res


from collections import deque

class Solution:

	def maxOfMin(self, arr, n):
		stack = []
		left = [-1] * (n + 1)
		right = [n] * (n + 1)
		for x in range(n):
			while stack and arr[stack[-1]] >= arr[x]:
				stack.pop()
			if stack:
				left[x] = stack[-1]
			stack.append(x)
		stack = []
		for x in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[x]:
				stack.pop()
			if stack:
				right[x] = stack[-1]
			stack.append(x)
		ans = [0 for x in range(n + 1)]
		for x in range(n):
			f = right[x] - left[x] - 1
			ans[f] = max(ans[f], arr[x])
		for x in range(n - 1, 0, -1):
			ans[x] = max(ans[x], ans[x + 1])
		return ans[1:n + 1]


class Solution:

	def nsr_fun(self, arr, n):
		stk = []
		ans = []
		i = n - 1
		while i >= 0:
			if len(stk) == 0:
				ans.append(n)
			elif arr[stk[-1]] < arr[i]:
				ans.append(stk[-1])
			else:
				while len(stk) > 0 and arr[stk[-1]] >= arr[i]:
					stk.pop()
				if len(stk) <= 0:
					ans.append(n)
				else:
					ans.append(stk[-1])
			stk.append(i)
			i -= 1
		ans.reverse()
		return ans

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

	def maxOfMin(self, arr, n):
		max_ele = 0
		nsl_arr = self.nsl_fun(arr, n)
		nsr_arr = self.nsr_fun(arr, n)
		ans_arr = [0 for j in range(n)]
		for i in range(n):
			max_ele = max(arr[i], max_ele)
			lft_indx = nsl_arr[i]
			rht_indx = nsr_arr[i]
			indx = rht_indx - lft_indx - 2
			ans_arr[indx] = max(arr[i], ans_arr[indx])
		ans_arr[0] = max_ele
		i = n - 2
		while i >= 0:
			ans_arr[i] = max(ans_arr[i], ans_arr[i + 1])
			i -= 1
		return ans_arr


class Solution:

	def maxOfMin(self, l, n):
		a = [n for _ in range(n)]
		s = []
		for i in range(n - 1, -1, -1):
			while s and l[s[-1]] >= l[i]:
				s.pop(-1)
			if s:
				a[i] = s[-1]
			s.append(i)
		b = [-1 for _ in range(n)]
		s = []
		for i in range(n):
			while s and l[s[-1]] >= l[i]:
				s.pop(-1)
			if s:
				b[i] = s[-1]
			s.append(i)
		ans = [0 for _ in range(n)]
		for i in range(n):
			x = a[i] - b[i] - 1
			ans[x - 1] = max(ans[x - 1], l[i])
		for i in range(n - 2, -1, -1):
			ans[i] = max(ans[i], ans[i + 1])
		return ans


class Solution:

	def maxOfMin(self, arr, n):
		stack = []
		right = [-1 for i in range(n)]
		stack.append(n - 1)
		for i in range(n - 2, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				right[i] = stack[-1]
			stack.append(i)
		stack = []
		left = [-1 for i in range(n)]
		stack.append(0)
		for i in range(1, n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				left[i] = stack[-1]
			stack.append(i)
		res = [-2 ** 31 for i in range(n)]
		for i in range(n):
			p = 0
			if left[i] == -1:
				p = max(p, i + 1)
			else:
				p = max(p, i - left[i])
			q = 0
			if right[i] == -1:
				q = max(q, n - i)
			else:
				q = max(q, right[i] - i)
			maxi = p + q - 1
			res[maxi - 1] = max(res[maxi - 1], arr[i])
		for i in range(n - 2, -1, -1):
			res[i] = max(res[i], res[i + 1])
		return res