Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly a_{i} feet high. 

 [Image] 

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.

Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.


-----Input-----

The first line of input contains integer n (1 ≤ n ≤ 2 × 10^5), the number of bears.

The second line contains n integers separated by space, a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), heights of bears.


-----Output-----

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.


-----Examples-----
Input
10
1 2 3 4 5 4 3 2 1 6

Output
6 4 4 3 3 2 2 1 1 1

Difficulty: HARD
Tags: Spanning trees

Sorting

Data structures

Dynamic programming
Skill types: Dynamic programming

Sorting

Data structures

Starter code:

Solutions:
n = int(input())
arr = list(map(int, input().split()))
(pse, nse) = ([-1] * n, [n] * n)
(stack, stack2) = ([0], [n - 1])
for i in range(1, n):
	while len(stack) and arr[i] < arr[stack[-1]]:
		nse[stack.pop()] = i
	stack.append(i)
	while len(stack2) and arr[n - i - 1] < arr[stack2[-1]]:
		pse[stack2.pop()] = n - i - 1
	stack2.append(n - i - 1)
dic = {}
for i in range(n):
	dic[arr[i]] = max(dic.get(arr[i], 0), nse[i] - pse[i] - 1)
k = list(dic.items())
k.sort(reverse=True, key=lambda x: x[0])
cnt = 0
for (ind, (item, times)) in enumerate(k):
	times -= cnt
	for _ in range(times):
		cnt += 1
		print(item, end=' ')


n = int(input())
r = [0] * (n + 1)
s = [(0, 0)]
a = [0] + list(map(int, input().split())) + [0]
for i in range(1, n + 2):
	while a[i] < s[-1][0]:
		r[i - s[-2][1] - 1] = max(s[-1][0], r[i - s[-2][1] - 1])
		del s[-1]
	s += [(a[i], i)]
for i in range(n):
	r[-i - 2] = max(r[-i - 2], r[-i - 1])
for i in range(1, n + 1):
	print(r[i], end=' ')


n = int(input())
maxn = n + 10
(dpl, dpr, ans) = ([0] * maxn, [n + 1] * maxn, [0] * maxn)
a = [0]
a.extend(list(map(int, input().split())))
a.append(0)
for i in range(1, n + 1):
	tmp = i - 1
	while a[tmp] >= a[i]:
		tmp = dpl[tmp]
	dpl[i] = tmp
for i in range(n, 0, -1):
	tmp = i + 1
	while a[tmp] >= a[i]:
		tmp = dpr[tmp]
	dpr[i] = tmp
	ans[dpr[i] - dpl[i] - 1] = max(ans[dpr[i] - dpl[i] - 1], a[i])
for i in range(n, 0, -1):
	ans[i] = max(ans[i + 1], ans[i])
print(' '.join(map(str, ans[1:n + 1])))


n = int(input().strip())
a = list(map(int, input().strip().split()))
ans = [0] * (n + 1)
a = [0] + a + [0]
s = []
for (index, value) in enumerate(a):
	while s and value < s[-1][0]:
		ans[index - s[-2][1] - 1] = max(s[-1][0], ans[index - s[-2][1] - 1])
		s.pop()
	s.append((value, index))
ans = ans[::-1]
for i in range(n):
	ans[i + 1] = max(ans[i + 1], ans[i])
ans = ans[::-1]
print(' '.join(map(str, ans[1:])))


N = int(input())
a = list(map(int, input().split()))
res = [0 for i in range(N + 1)]
st = [(0, -1)]
for (i, hh) in enumerate(a):
	while st[-1][0] >= hh:
		num = st[-1][0]
		st.pop()
		ll = i - st[-1][1] - 1
		res[ll] = max(res[ll], num)
	st.append((hh, i))
while len(st) > 1:
	num = st[-1][0]
	st.pop()
	ll = N - st[-1][1] - 1
	res[ll] = max(res[ll], num)
for i in range(N - 1, 0, -1):
	res[i] = max(res[i], res[i + 1])
print(' '.join(map(str, res[1:])))


import math
import random

class AVLTree:

	def __init__(self, x):
		self.left = None
		self.rght = None
		self.val = x
		self.height = 1

def getHeight0(root):
	if root == None:
		return 0
	return max(getHeight0(root.left), getHeight0(root.rght)) + 1

def getHeight(root):
	if root == None:
		return 0
	return root.height

def insert(root, x):
	if root == None:
		return AVLTree(x)
	if x == root.val:
		return root
	if x < root.val:
		root.left = insert(root.left, x)
	elif x > root.val:
		root.rght = insert(root.rght, x)
	hl = getHeight(root.left)
	hr = getHeight(root.rght)
	root.height = max(hl, hr) + 1
	if hr - hl > 1:
		assert hr - hl == 2
		hrr = getHeight(root.rght.rght)
		hrl = getHeight(root.rght.left)
		if hrr == hrl + 1:
			new_root = root.rght
			root.rght = new_root.left
			new_root.left = root
			root.height -= 2
			return new_root
		elif hrl == hrr + 1:
			new_root = root.rght.left
			root.rght.left = new_root.rght
			new_root.rght = root.rght
			root.rght = new_root.left
			new_root.left = root
			root.height -= 2
			new_root.height += 1
			new_root.rght.height -= 1
			return new_root
		else:
			assert False
	elif hl - hr > 1:
		assert hl - hr == 2
		hlr = getHeight(root.left.rght)
		hll = getHeight(root.left.left)
		if hll == hlr + 1:
			new_root = root.left
			root.left = new_root.rght
			new_root.rght = root
			root.height -= 2
			return new_root
		elif hlr == hll + 1:
			new_root = root.left.rght
			root.left.rght = new_root.left
			new_root.left = root.left
			root.left = new_root.rght
			new_root.rght = root
			root.height -= 2
			new_root.height += 1
			new_root.left.height -= 1
			return new_root
		else:
			assert False
	return root

def findUpperBound(root, x):
	if root == None:
		return None
	if x >= root.val:
		return findUpperBound(root.rght, x)
	tmp_bound = findUpperBound(root.left, x)
	if tmp_bound == None:
		return root.val
	return tmp_bound

def findLowerBound(root, x):
	if root == None:
		return None
	if x <= root.val:
		return findLowerBound(root.left, x)
	tmp_bound = findLowerBound(root.rght, x)
	if tmp_bound == None:
		return root.val
	return tmp_bound

def inorder(root):
	if root == None:
		return []
	return inorder(root.left) + [root.val] + inorder(root.rght)

def checkHeight(root):
	if root == None:
		return True
	if not checkHeight(root.left):
		return False
	if not checkHeight(root.rght):
		return False
	return abs(getHeight0(root.left) - getHeight0(root.rght)) <= 1

def testAVL():
	l = [x for x in range(100)]
	for i in range(100):
		ni = random.randint(0, 99)
		(l[i], l[ni]) = (l[ni], l[i])
	tree = None
	for v in l:
		tree = insert(tree, v)
	assert inorder(tree) == [i for i in range(100)]
	assert checkHeight(tree) == True

class HeapObj:

	def __init__(self, v, n):
		self.val = v
		self.hpidx = n

def shiftup(n, r, hp):
	while r >= 0:
		j = r * 2 + 1
		if j < n:
			if j + 1 < n and hp[j + 1].val > hp[j].val:
				j += 1
			if hp[j].val <= hp[r].val:
				return
			(hp[r], hp[j]) = (hp[j], hp[r])
			hp[r].hpidx = r
			hp[j].hpidx = j
		if r == 0:
			break
		r = int((r - 1) / 2)

def shiftdown(n, r, hp):
	while r < n:
		j = r * 2 + 1
		if j >= n:
			return
		if j + 1 < n and hp[j + 1].val > hp[j].val:
			j += 1
		if hp[j].val <= hp[r].val:
			return
		(hp[r], hp[j]) = (hp[j], hp[r])
		hp[r].hpidx = r
		hp[j].hpidx = j
		r = j

def testHeap():
	hp = []
	for _ in range(100):
		obj = HeapObj(random.randint(0, 9999), len(hp))
		hp.append(obj)
		shiftup(len(hp), len(hp) - 1, hp)
	res = []
	while hp:
		res.append(hp[0].val)
		(hp[0], hp[-1]) = (hp[-1], hp[0])
		hp[0].hpidx = 0
		hp.pop()
		shiftdown(len(hp), 0, hp)
	assert res == sorted(res, reverse=True)

def calc(n, a):
	ia = [x for x in enumerate(a)]
	ia.sort(key=lambda tp: tp[1])
	tree = None
	tree = insert(tree, -1)
	tree = insert(tree, n)
	hpobj = HeapObj(n, 0)
	hp = [hpobj]
	itv2hpobj = {(0, n - 1): hpobj}
	ret = []
	nxt = n
	for (idx, val) in ia:
		interval_end = findUpperBound(tree, idx) - 1
		interval_bgn = findLowerBound(tree, idx) + 1
		itv = (interval_bgn, interval_end)
		assert itv in itv2hpobj
		tree = insert(tree, idx)
		itv2hpobj[itv].val = 2 * n
		hpidx = itv2hpobj[itv].hpidx
		shiftup(len(hp), hpidx, hp)
		(hp[0], hp[-1]) = (hp[-1], hp[0])
		hp[0].hpidx = 0
		hp.pop()
		del itv2hpobj[itv]
		shiftdown(len(hp), 0, hp)
		if idx > interval_bgn:
			new_obj = HeapObj(idx - interval_bgn, len(hp))
			hp.append(new_obj)
			itv2hpobj[interval_bgn, idx - 1] = new_obj
			shiftup(len(hp), len(hp) - 1, hp)
		if idx < interval_end:
			new_obj = HeapObj(interval_end - idx, len(hp))
			hp.append(new_obj)
			itv2hpobj[idx + 1, interval_end] = new_obj
			shiftup(len(hp), len(hp) - 1, hp)
		NA = 0
		if len(hp) > 0:
			NA = hp[0].val
		while nxt > NA:
			ret.append(val)
			nxt -= 1
	assert len(ret) == n
	ret.reverse()
	return ret

def calc_bf(n, a):
	ans = [None for _ in range(n)]
	for i in range(n):
		minij = None
		for j in range(i, n):
			l = j - i
			if minij == None or minij > a[j]:
				minij = a[j]
			if ans[l] == None or ans[l] < minij:
				ans[l] = minij
	return ans

def duipai():
	n = 10
	a = [random.randint(1, 20) for _ in range(n)]
	res_smt = calc2(n, a)
	res_btf = calc_bf(n, a)
	if res_smt != res_btf:
		print('!')
		print(a)
		print(res_smt)
		print(res_btf)
		return False
	return True

def duipai_n(times):
	for i in range(times):
		print('Att {t}'.format(t=i))
		if not duipai():
			break
		print()

def calc2(n, a):
	ans = [None for _ in range(n)]
	bst_intvs = [None for _ in range(n)]
	stk = [(-1, -2)]
	for (idx, v) in enumerate(a + [-1]):
		while v <= stk[-1][1]:
			bst_intvs[stk[-1][0]] = idx - stk[-2][0] - 2
			stk.pop()
		stk.append((idx, v))
	for i in range(n):
		iv = bst_intvs[i]
		if ans[iv] == None or ans[iv] < a[i]:
			ans[iv] = a[i]
	for i in range(n - 2, -1, -1):
		if ans[i] == None or ans[i] < ans[i + 1]:
			ans[i] = ans[i + 1]
	return ans

def serious():
	n = int(input())
	a = [int(x) for x in input().split()]
	res = calc2(n, a)
	ans = ''
	for x in res[:-1]:
		ans += str(x) + ' '
	ans += str(res[-1])
	print(ans)

def main():
	serious()

def __starting_point():
	main()
__starting_point()


from sys import stdin, stdout

def input():
	return stdin.readline().strip()

def print(x, end='\n'):
	stdout.write(str(x) + end)
(n, lst) = (int(input()), list(map(int, input().split())))
(nse, pse, stk, ans) = ([n for i in range(n)], [-1 for i in range(n)], [], [0 for i in range(n)])
for i in range(n):
	while stk and lst[stk[-1]] > lst[i]:
		nse[stk.pop()] = i
	stk.append(i)
stk.clear()
for i in range(n - 1, -1, -1):
	while stk and lst[stk[-1]] > lst[i]:
		pse[stk.pop()] = i
	stk.append(i)
for i in range(n):
	ans[nse[i] - pse[i] - 2] = max(lst[i], ans[nse[i] - pse[i] - 2])
for i in range(n - 2, -1, -1):
	ans[i] = max(ans[i + 1], ans[i])
print(' '.join(map(str, ans)))


n = int(input())
arr = list(map(int, input().split()))
stack = []
left = [0 for i in range(n)]
right = [0 for i in range(n)]
for i in range(n):
	while stack and arr[i] <= arr[stack[-1]]:
		stack.pop()
	left[i] = i - stack[-1] - 1 if stack else i
	stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
	while stack and arr[i] <= arr[stack[-1]]:
		stack.pop()
	right[i] = stack[-1] - i if stack else n - i
	stack.append(i)
ans = [0 for i in range(n + 1)]
for i in range(n):
	ans[left[i] + right[i]] = max(ans[left[i] + right[i]], arr[i])
for i in range(n - 1, 0, -1):
	ans[i] = max(ans[i], ans[i + 1])
mini = 9999999999999
for i in range(1, n + 1):
	if ans[i] == 0:
		print(mini, end=' ')
	else:
		print(ans[i], end=' ')
		mini = ans[i]
print()


from collections import deque

class Solution:

	def minmax(heights):
		(fwd_queue, bwd_queue) = (deque(), deque())
		(fwd_high, bwd_high) = (list(range(len(heights))), list(range(len(heights))))
		for i in range(len(heights)):
			while len(bwd_queue) > 0 and heights[bwd_queue[-1]] >= heights[i]:
				bwd_queue.pop()
			bwd_high[i] = bwd_queue[-1] if len(bwd_queue) > 0 else -1
			bwd_queue.append(i)
		for i in range(len(heights) - 1, -1, -1):
			while len(fwd_queue) > 0 and heights[fwd_queue[-1]] >= heights[i]:
				fwd_queue.pop()
			fwd_high[i] = fwd_queue[-1] if len(fwd_queue) > 0 else len(heights)
			fwd_queue.append(i)
		height_ranges = sorted([(heights[i], fwd_high[i] - bwd_high[i] - 1) for i in range(len(heights))], reverse=True)
		result = [0] * (len(heights) + 1)
		for (height, length) in height_ranges:
			while length > 0 and result[length] == 0:
				result[length] = height
				length -= 1
		return result
n = int(input())
arr = list(map(int, input().strip().split(' ')))
print(' '.join(map(str, Solution.minmax(arr)[1:])))


import sys

def main():
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	dq = []
	left_nearest = [-1] * n
	right_nearest = [n] * n
	for i in range(n):
		while len(dq) and a[dq[-1]] >= a[i]:
			del dq[-1]
		if len(dq):
			left_nearest[i] = dq[-1]
		dq.append(i)
	dq.clear()
	for i in range(n - 1, -1, -1):
		while len(dq) and a[dq[-1]] >= a[i]:
			del dq[-1]
		if len(dq):
			right_nearest[i] = dq[-1]
		dq.append(i)
	ans = [-1] * (n + 1)
	for i in range(n):
		length = right_nearest[i] - i + i - left_nearest[i] - 1
		ans[length] = max(ans[length], a[i])
	for i in range(n - 1, 0, -1):
		ans[i] = max(ans[i], ans[i + 1])
	sys.stdout.write(' '.join(map(str, ans[1:])))
main()


N = int(input())
array = list(map(int, input().split()))
res = [0 for i in range(N + 1)]
stack = [(0, -1)]
for (i, height) in enumerate(array):
	while stack[-1][0] >= height:
		num = stack[-1][0]
		stack.pop()
		length = i - stack[-1][1] - 1
		res[length] = max(res[length], num)
	stack.append((height, i))
while len(stack) > 1:
	num = stack[-1][0]
	stack.pop()
	length = N - stack[-1][1] - 1
	res[length] = max(res[length], num)
for i in range(N - 1, 0, -1):
	res[i] = max(res[i], res[i + 1])
print(' '.join(map(str, res[1:])))


btqAIXPWRsBVCLo = int
btqAIXPWRsBVCLE = input
btqAIXPWRsBVCLp = list
btqAIXPWRsBVCLT = map
btqAIXPWRsBVCLN = range
btqAIXPWRsBVCLJ = max
btqAIXPWRsBVCLD = print
btqAIXPWRsBVCLy = str
btqAIXPWRsBVCLM = btqAIXPWRsBVCLo
btqAIXPWRsBVCLj = btqAIXPWRsBVCLE
btqAIXPWRsBVCLu = btqAIXPWRsBVCLp
btqAIXPWRsBVCLH = btqAIXPWRsBVCLT
btqAIXPWRsBVCLr = btqAIXPWRsBVCLN
btqAIXPWRsBVCLm = btqAIXPWRsBVCLJ
btqAIXPWRsBVCLa = btqAIXPWRsBVCLD
btqAIXPWRsBVCLf = btqAIXPWRsBVCLy
n = btqAIXPWRsBVCLM(btqAIXPWRsBVCLj())
r = [0] * (n + 1)
a = [0] * (n + 1)
a[1:-1] = btqAIXPWRsBVCLu(btqAIXPWRsBVCLH(btqAIXPWRsBVCLM, btqAIXPWRsBVCLj().split()))
s = [(0, 0)]
for i in btqAIXPWRsBVCLr(1, n + 2):
	while a[i] < s[-1][0]:
		r[i - s[-2][1] - 1] = btqAIXPWRsBVCLm(s[-1][0], r[i - s[-2][1] - 1])
		del s[-1]
	s += [(a[i], i)]
for i in btqAIXPWRsBVCLr(n):
	r[-i - 2] = btqAIXPWRsBVCLm(r[-i - 2], r[-i - 1])
btqAIXPWRsBVCLa(' '.join(btqAIXPWRsBVCLH(btqAIXPWRsBVCLf, r[1:])))


import math
import random
import string
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=300006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
n = int(input())
q = []
q.append((-1, -1))
l = list(map(int, input().split()))
left = [0] * n
for i in range(n):
	while q[-1][0] >= l[i]:
		q.pop()
	left[i] = q[-1][1]
	q.append((l[i], i))
q = []
q.append((-1, n))
right = [0] * n
for i in range(n - 1, -1, -1):
	while q[-1][0] >= l[i]:
		q.pop()
	right[i] = q[-1][1]
	q.append((l[i], i))
len = [0] * n
li = []
heapq.heapify(li)
for i in range(n):
	len[i] = i - left[i] + (right[i] - i) - 1
	heapq.heappush(li, (-l[i], len[i]))
ans = [0] * n
cur = 1
for i in range(n - 1, -1, -1):
	(e, le) = heapq.heappop(li)
	e *= -1
	while cur <= le:
		ans[cur - 1] = e
		cur += 1
print(*ans)


n = list(map(int, input().split()))[0]
lst = list(map(int, input().split()))
sorted_index = sorted(range(n), key=lambda k: lst[k], reverse=True)
lookup = [(0, 0)] * n
res = []
res_pos = 1
for index in sorted_index:
	seq_len = lookup[index][0] + lookup[index][1] + 1
	if seq_len >= res_pos:
		step = seq_len - res_pos + 1
		res += [lst[index]] * step
		res_pos += step
	step_back = lookup[index][0] + 1
	if index - step_back >= 0:
		lookup[index - step_back] = (lookup[index - step_back][0], lookup[index - step_back][1] + 1 + lookup[index][1])
	step_forward = lookup[index][1] + 1
	if index + step_forward < n:
		lookup[index + step_forward] = (lookup[index + step_forward][0] + 1 + lookup[index][0], lookup[index + step_forward][1])
res = list(map(str, res))
print(' '.join(res))


def VI():
	return list(map(int, input().split()))

def main_old(n, a):
	s = list(a)
	print(max(a), end=' ')
	for i in range(1, n):
		ns = list(s[:-1])
		mx = 0
		for j in range(len(ns)):
			ns[j] = min(s[j], s[j + 1])
			if ns[j] > mx:
				mx = ns[j]
		s = ns
		print(mx, end=' ')
from sys import stdout

def main(n, a):
	s = a
	buf = str(max(a))
	for i in range(n - 1, 0, -1):
		mx = 0
		for j in range(i):
			s[j] = min(s[j], s[j + 1])
			if s[j] > mx:
				mx = s[j]
		buf += ' ' + str(mx)
	stdout.write(buf + '\n')

def run(n, a):
	stack = []
	(l, r) = ([0] * n, [0] * n)
	for x in range(n):
		while len(stack) > 0 and a[stack[-1]] >= a[x]:
			stack.pop()
		if len(stack) == 0:
			l[x] = -1
		else:
			l[x] = stack[-1]
		stack.append(x)
	stack = []
	for x in range(n - 1, -1, -1):
		while len(stack) > 0 and a[stack[-1]] >= a[x]:
			stack.pop()
		if len(stack) == 0:
			r[x] = n
		else:
			r[x] = stack[-1]
		stack.append(x)
	sl = [-1] * n
	for x in range(n):
		v = r[x] - l[x] - 1
		sl[v - 1] = max(sl[v - 1], a[x])
	for x in range(n - 2, -1, -1):
		sl[x] = max(sl[x], sl[x + 1])
	print(' '.join([str(x) for x in sl]))

def main_input(info=0):
	n = int(input())
	a = VI()
	run(n, a)
main_input()


n = int(input())
a = [0] + list(map(int, input().split())) + [0]
r = [0] * (n + 1)
st = [(0, 0)]
for i in range(1, n + 2):
	while a[i] < st[-1][0]:
		r[i - st[-2][1] - 1] = max(st[-1][0], r[i - st[-2][1] - 1])
		st.pop()
	st.append((a[i], i))
for i in range(n):
	r[-i - 2] = max(r[-i - 2], r[-i - 1])
print(*r[1:])


n = int(input())
ar = list(map(int, input().split()))
prev_smaller = [i + 1 for i in range(n)]
next_smaller = [n + 1] * n
stack = []
for (index, value) in enumerate(ar):
	while stack and ar[stack[-1]] >= value:
		stack.pop()
	if stack:
		prev_smaller[index] = stack[-1] + 1
	else:
		prev_smaller[index] = 0
	stack.append(index)
stack = []
for index in range(n - 1, -1, -1):
	while stack and ar[stack[-1]] >= ar[index]:
		stack.pop()
	if stack:
		next_smaller[index] = stack[-1] + 1
	stack.append(index)
min_elm = min(ar)
ans = [min_elm for _ in range(n + 1)]
for i in range(n):
	sz = next_smaller[i] - prev_smaller[i] - 1
	ans[sz] = max(ans[sz], ar[i])
for i in range(n - 1, 0, -1):
	ans[i] = max(ans[i], ans[i + 1])
print(*ans[1:])


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
l = [-1] * n
r = [n] * n
stack = []
for i in range(n):
	while stack and a[stack[-1]] >= a[i]:
		stack.pop()
	if stack:
		l[i] = stack[-1]
	stack.append(i)
stack = []
for i in range(n)[::-1]:
	while stack and a[stack[-1]] >= a[i]:
		stack.pop()
	if stack:
		r[i] = stack[-1]
	stack.append(i)
ans = [min(a)] * n
for i in range(n):
	d = r[i] - l[i] - 2
	ans[d] = max(ans[d], a[i])
val = min(a)
for i in range(n)[::-1]:
	val = max(val, ans[i])
	ans[i] = val
print(*ans)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, A):
	A = [float('inf')] + A + [float('inf')]
	left = [0 for i in range(N + 2)]
	right = [N + 1 for i in range(N + 2)]
	q = []
	for (i, v) in enumerate(A):
		while q and q[-1][1] > v:
			(j, u) = q.pop()
			right[j] = i
		if q:
			(j, u) = q[-1]
			left[i] = j
		q.append((i, v))
	ans = [0 for _ in range(N + 1)]
	p = [0 for _ in range(N + 2)]
	for (i, v) in enumerate(A):
		l = right[i] - left[i] - 1
		p[l] = max(p[l], v)
	maxv = 0
	for i in range(N, -1, -1):
		maxv = max(p[i], maxv)
		ans[i] = maxv
	print(' '.join(map(str, ans[1:])))
N = int(input())
A = [int(x) for x in input().split()]
solve(N, A)


n = int(input())
s = list(map(int, input().split()))
output = [len(s)] * len(s)
stack = []
stack.append(0)
for i in range(1, len(s)):
	if stack and s[stack[-1]] <= s[i]:
		stack.append(i)
	else:
		while stack and s[stack[-1]] > s[i]:
			output[stack[-1]] = i
			stack.pop()
		stack.append(i)
output1 = [-1] * len(s)
stack = []
stack.append(len(s) - 1)
for i in range(len(s) - 2, -1, -1):
	if stack and s[stack[-1]] <= s[i]:
		stack.append(i)
	else:
		while stack and s[stack[-1]] > s[i]:
			output1[stack[-1]] = i
			stack.pop()
		stack.append(i)
res = [0] * (len(s) + 1)
for i in range(len(s)):
	res[output[i] - output1[i] - 1] = max(res[output[i] - output1[i] - 1], s[i])
for i in range(len(res) - 2, -1, -1):
	res[i] = max(res[i], res[i + 1])
print(*res[1:])


n = int(input())
arr = list(map(int, input().split()))
arr = [0] + arr + [0]
suffmin = [n + 1] * (n + 2)
premin = [0] * (n + 1)
st = [n + 1]
for i in range(1, n + 1):
	while arr[i] < arr[st[-1]]:
		suffmin[st[-1]] = i
		st.pop()
	st += [i]
st = [0]
for i in range(n, 0, -1):
	while arr[i] < arr[st[-1]]:
		premin[st[-1]] = i
		st.pop()
	st += [i]
maxans = [0] * (n + 2)
for i in range(1, n + 1):
	if maxans[suffmin[i] - premin[i] - 1] < arr[i]:
		maxans[suffmin[i] - premin[i] - 1] = arr[i]
m = arr[1]
for i in range(1, n + 1):
	if arr[i] < m:
		m = arr[i]
maxans[n] = m
for i in range(n - 1, 0, -1):
	if maxans[i + 1] > maxans[i]:
		maxans[i] = maxans[i + 1]
print(*maxans[1:n + 1])


def printMaxOfMin(arr, n):
	stack = []
	left_smaller = [-1] * (n + 1)
	right_smaller = [n] * (n + 1)
	for i in range(n):
		while stack and arr[stack[-1]] >= arr[i]:
			stack.pop()
		if stack:
			left_smaller[i] = stack[-1]
		stack.append(i)
	while stack:
		stack.pop()
	for i in range(n - 1, -1, -1):
		while stack and arr[stack[-1]] >= arr[i]:
			stack.pop()
		if stack:
			right_smaller[i] = stack[-1]
		stack.append(i)
	ans = [0] * (n + 1)
	for i in range(n):
		window = right_smaller[i] - left_smaller[i] - 1
		ans[window] = max(ans[window], arr[i])
	for i in range(n - 1, -1, -1):
		ans[i] = max(ans[i], ans[i + 1])
	return ans[1:]
n = int(input())
arr = [int(i) for i in input().split()]
for i in printMaxOfMin(arr, n):
	print(i, end=' ')
print('')


def read_data():
	n = int(input())
	hs = list(map(int, input().split()))
	return (n, hs)

def solve(n, hs):
	left = get_left_index(n, hs)
	right = get_right_index(n, hs)
	vals = [[] for i in range(n)]
	for (h, l, r) in zip(hs, left, right):
		vals[r - l - 2].append(h)
	min_hs = []
	min_h = -float('inf')
	for val in vals[::-1]:
		for v in val:
			min_h = max(min_h, v)
		min_hs.append(min_h)
	print(*min_hs[::-1])

def get_left_index(n, hs):
	left = []
	stack = []
	for (i, h) in enumerate(hs):
		while stack and hs[stack[-1]] >= h:
			del stack[-1]
		if stack:
			left.append(stack[-1])
		else:
			left.append(-1)
		stack.append(i)
	return left

def get_right_index(n, hs):
	hs.reverse()
	tmp = get_left_index(n, hs)
	hs.reverse()
	tmp.reverse()
	right = [n - 1 - a for a in tmp]
	return right
(n, hs) = read_data()
solve(n, hs)


n = int(input())
arr = list(map(int, input().split()))
(pse, nse) = ([-1] * n, [n] * n)
(stack, stack2) = ([0], [n - 1])
for i in range(1, n):
	while len(stack) and arr[i] < arr[stack[-1]]:
		nse[stack.pop()] = i
	stack.append(i)
	while len(stack2) and arr[n - i - 1] < arr[stack2[-1]]:
		pse[stack2.pop()] = n - i - 1
	stack2.append(n - i - 1)
dic = {}
for i in range(n):
	dic[arr[i]] = max(dic.get(arr[i], 0), nse[i] - pse[i] - 1)
out = [0] * (n + 1)
for i in dic:
	out[dic[i]] = max(out[dic[i]], i)
temp = out[-1]
for i in range(n - 1, 0, -1):
	if out[i] < out[i + 1]:
		out[i] = out[i + 1]
print(' '.join(map(str, out[1:])))


N = input()
N = int(N)
A = input().split(' ')
A = list(map(int, A))

def get_L(A):
	L_candidates = []
	L = A[:]
	for i in range(len(A)):
		while L_candidates and A[L_candidates[-1]] >= A[i]:
			L_candidates.pop()
		if L_candidates:
			L[i] = L_candidates[-1]
		else:
			L[i] = -1
		L_candidates.append(i)
	return L
L = get_L(A)
R = [N - x - 1 for x in get_L(A[::-1])][::-1]
strengths = [0] * (N + 3)
for i in range(N):
	p = R[i] - L[i] - 1
	strengths[p] = max(strengths[p], A[i])
strengths = strengths[1:N + 1]
strengths = strengths[::-1]
for i in range(1, N):
	strengths[i] = max(strengths[i], strengths[i - 1])
strengths = strengths[::-1]
print(' '.join(map(str, strengths)))


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	arr = [0] + list(map(int, input().split())) + [0]
	left = [0] * (n + 3)
	right = [n + 1] * (n + 3)
	ans = [0] * (n + 3)
	for i in range(1, n + 1):
		z = i - 1
		while arr[z] >= arr[i]:
			z = left[z]
		left[i] = z
	for i in range(n, 0, -1):
		z = i + 1
		while arr[z] >= arr[i]:
			z = right[z]
		right[i] = z
		ans[right[i] - left[i] - 1] = max(ans[right[i] - left[i] - 1], arr[i])
	for i in range(n, 0, -1):
		ans[i] = max(ans[i + 1], ans[i])
	print(*ans[1:n + 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
a = list(map(int, input().split()))
stack = []
ans = [0] * n
l = [-1] * n
r = [n] * n
for i in range(n):
	while stack and a[i] <= a[stack[-1]]:
		stack.pop()
	if stack:
		l[i] = stack[-1]
	stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
	while stack and a[i] <= a[stack[-1]]:
		stack.pop()
	if stack:
		r[i] = stack[-1]
	stack.append(i)
for i in range(n):
	Len = r[i] - l[i] - 1
	Len -= 1
	ans[Len] = max(ans[Len], a[i])
for i in range(n - 2, -1, -1):
	ans[i] = max(ans[i], ans[i + 1])
print(*ans)


numFeet = int(input())
arr = list(map(int, input().split()))
stack = []
r_arr = [numFeet] * (numFeet + 1)
l_arr = [-1] * (numFeet + 1)
ans = [0] * (numFeet + 1)
for i in range(numFeet):
	while stack and arr[stack[-1]] >= arr[i]:
		stack.pop()
	if stack:
		l_arr[i] = stack[-1]
	stack.append(i)
while stack:
	stack.pop()
for i in range(numFeet - 1, -1, -1):
	while stack and arr[stack[-1]] >= arr[i]:
		stack.pop()
	if stack:
		r_arr[i] = stack[-1]
	stack.append(i)
for i in range(numFeet):
	temp = r_arr[i] - l_arr[i] - 1
	ans[temp] = max(arr[i], ans[temp])
for i in range(numFeet - 1, -1, -1):
	ans[i] = max(ans[i + 1], ans[i])
for x in ans[1:]:
	print(x, end=' ')


n = int(input())
l = [int(i) for i in input().split()]
stack = []
ans = [0] * n
left = [-1] * n
right = [n] * n
for i in range(n):
	while stack != [] and l[i] <= l[stack[-1]]:
		stack.pop()
	if stack != []:
		left[i] = stack[-1]
	stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
	while stack != [] and l[i] <= l[stack[-1]]:
		stack.pop()
	if stack != []:
		right[i] = stack[-1]
	stack.append(i)
for i in range(n):
	k = right[i] - left[i] - 1
	ans[k - 1] = max(ans[k - 1], l[i])
for i in range(n - 2, -1, -1):
	ans[i] = max(ans[i], ans[i + 1])
print(*ans)


__author__ = 'kitkat'
import sys
MAXN = int(200000.0 + 10)
try:
	while True:
		S = [0] * MAXN
		ans = [0] * MAXN
		L = [0] * MAXN
		R = [0] * MAXN
		n = int(input())
		val = list(map(int, input().split(' ')))
		top = -1
		for i in range(n):
			while ~top and val[i] <= val[S[top]]:
				top -= 1
			L[i] = S[top] if ~top else -1
			top += 1
			S[top] = i
		top = -1
		for i in range(n - 1, -1, -1):
			while ~top and val[i] <= val[S[top]]:
				top -= 1
			R[i] = S[top] if ~top else n
			top += 1
			S[top] = i
		for i in range(n):
			ans[R[i] - L[i] - 1] = max(ans[R[i] - L[i] - 1], val[i])
		for i in range(n - 1, 0, -1):
			ans[i] = max(ans[i], ans[i + 1])
		for i in range(1, n + 1):
			sys.stdout.write('%d ' % ans[i])
		print('')
except EOFError:
	pass


import random, math, sys
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
from collections import Counter
input = sys.stdin.readline

def solution(li):
	n = len(li)
	pse = [-1] * n
	nse = [n + 1 - 1] * n
	stack = []
	for i in range(len(li)):
		if stack and li[stack[-1]] < li[i]:
			stack.append(i)
		else:
			while stack and li[stack[-1]] > li[i]:
				tmp = stack.pop()
				nse[tmp] = i + 1 - 1
			stack.append(i)
	stack = []
	for i in range(len(li) - 1, -1, -1):
		if stack and li[stack[-1]] < li[i]:
			stack.append(i)
		else:
			while stack and li[stack[-1]] > li[i]:
				tmp = stack.pop()
				pse[tmp] = i + 1 - 1
			stack.append(i)
	mini = 0
	out = [-1] * n
	li1 = [[li[i], i] for i in range(n)]
	for i in range(n):
		y = nse[li1[i][1]]
		x = pse[li1[i][1]]
		cur = y - x - 1
		if li1[i][0] > out[cur - 1]:
			out[cur - 1] = li1[i][0]
		mini = max(mini, cur + 1 - 1)
	last = out[-1]
	for i in range(len(li) - 2, -1, -1):
		if out[i] == -1 or out[i] < last:
			out[i] = last + 1 - 1
		else:
			last = out[i] + 1 - 1
	return out

def input_test():
	n = int(input())
	li = list(map(int, input().strip().split(' ')))
	out = solution(li)
	print(*out)
input_test()


n = int(input())
a = [int(o) for o in input().split()]
l = [-1] * n
r = [n] * n
stack = []
for i in range(n):
	while stack and a[stack[-1]] >= a[i]:
		stack.pop()
	if stack:
		l[i] = stack[-1]
	stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
	while stack and a[stack[-1]] >= a[i]:
		stack.pop()
	if stack:
		r[i] = stack[-1]
	stack.append(i)
answers = [min(a)] * n
for i in range(n):
	lw = r[i] - l[i] - 2
	answers[lw] = max(answers[lw], a[i])
ans = min(a)
answers[0] = max(a)
for i in range(n - 1, -1, -1):
	ans = max(ans, answers[i])
	answers[i] = ans
print(*answers)


n = int(input())
arr = list(map(int, input().split()))
(left, right) = ([-1] * n, [n] * n)
ans = [0] * n
st = [0]
for i in range(1, n):
	while st and arr[st[-1]] >= arr[i]:
		st.pop()
	if st:
		left[i] = st[-1]
	st.append(i)
st = [n - 1]
for i in range(n - 2, -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):
	ans[right[i] - left[i] - 2] = max(ans[right[i] - left[i] - 2], arr[i])
ans[0] = max(arr)
ans[-1] = min(arr)
for i in range(n - 2, 0, -1):
	ans[i] = max(ans[i], ans[i + 1])
print(' '.join(map(str, ans)))


import sys

def solve():
	(n,) = rv()
	(h,) = rl(1)
	smallertoleftindex = [-1] * n
	smallertorightindex = [n] * n
	temp = list()
	for i in range(n):
		while len(temp) > 0 and h[temp[-1]] >= h[i]:
			temp.pop(-1)
		smallertoleftindex[i] = -1 if len(temp) == 0 else temp[-1]
		temp.append(i)
	temp = list()
	for i in range(n - 1, -1, -1):
		while len(temp) > 0 and h[temp[-1]] >= h[i]:
			temp.pop(-1)
		smallertorightindex[i] = n if len(temp) == 0 else temp[-1]
		temp.append(i)
	res = [0] * (n + 1)
	for i in range(n):
		nums = smallertorightindex[i] - smallertoleftindex[i] - 1
		res[nums] = max(res[nums], h[i])
	for i in range(n - 1, 0, -1):
		res[i] = max(res[i], res[i + 1])
	print(' '.join(map(str, res[1:])))

def prt(l):
	return print(''.join(l))

def rv():
	return map(int, input().split())

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


n = int(input())
arr = list(map(int, input().split()))
(left, right) = ([0 for index in range(n)], [0 for index in range(n)])
length = [0 for index in range(n)]
answer = [0 for index in range(n)]
stack = []
for index in range(n):
	while len(stack) > 0 and arr[stack[-1]] >= arr[index]:
		stack.pop()
	if len(stack) == 0:
		left[index] = -1
	else:
		left[index] = stack[-1]
	stack.append(index)
stack = []
for index in range(n - 1, -1, -1):
	while len(stack) > 0 and arr[stack[-1]] >= arr[index]:
		stack.pop()
	if len(stack) == 0:
		right[index] = n
	else:
		right[index] = stack[-1]
	stack.append(index)
for index in range(n):
	length[index] = right[index] - left[index] - 1
for index in range(n):
	answer[length[index] - 1] = max(answer[length[index] - 1], arr[index])
for index in range(n - 2, -1, -1):
	answer[index] = max(answer[index], answer[index + 1])
print(*answer)