This is a harder version of the problem. In this version $n \le 500\,000$

The outskirts of the capital are being actively built up in Berland. The company "Kernel Panic" manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along the highway. It is known that the company has already bought $n$ plots along the highway and is preparing to build $n$ skyscrapers, one skyscraper per plot.

Architects must consider several requirements when planning a skyscraper. Firstly, since the land on each plot has different properties, each skyscraper has a limit on the largest number of floors it can have. Secondly, according to the design code of the city, it is unacceptable for a skyscraper to simultaneously have higher skyscrapers both to the left and to the right of it.

Formally, let's number the plots from $1$ to $n$. Then if the skyscraper on the $i$-th plot has $a_i$ floors, it must hold that $a_i$ is at most $m_i$ ($1 \le a_i \le m_i$). Also there mustn't be integers $j$ and $k$ such that $j < i < k$ and $a_j > a_i < a_k$. Plots $j$ and $k$ are not required to be adjacent to $i$.

The company wants the total number of floors in the built skyscrapers to be as large as possible. Help it to choose the number of floors for each skyscraper in an optimal way, i.e. in such a way that all requirements are fulfilled, and among all such construction plans choose any plan with the maximum possible total number of floors.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 500\,000$) — the number of plots.

The second line contains the integers $m_1, m_2, \ldots, m_n$ ($1 \leq m_i \leq 10^9$) — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.


-----Output-----

Print $n$ integers $a_i$ — the number of floors in the plan for each skyscraper, such that all requirements are met, and the total number of floors in all skyscrapers is the maximum possible.

If there are multiple answers possible, print any of them.


-----Examples-----
Input
5
1 2 3 2 1

Output
1 2 3 2 1 

Input
3
10 6 8

Output
10 6 6 



-----Note-----

In the first example, you can build all skyscrapers with the highest possible height.

In the second test example, you cannot give the maximum height to all skyscrapers as this violates the design code restriction. The answer $[10, 6, 6]$ is optimal. Note that the answer of $[6, 6, 8]$ also satisfies all restrictions, but is not optimal.

Difficulty: HARD
Tags: Dynamic programming

Data structures

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
inf = float('inf')
n = int(input())
a = [-inf] + [int(i) for i in input().split()] + [-inf]
for x in (0, 1):
	stack = [0]
	ns = [-1] * (n + 2)
	for i in range(n, -1, -1):
		while a[i] < a[stack[-1]]:
			ns[stack.pop()] = i
		stack += [i]
	res = [0] * (n + 2)
	for i in range(1, len(a)):
		if ns[i] == 0:
			res[i] = i * a[i]
		else:
			res[i] = res[ns[i]] + a[i] * (i - ns[i])
	a = a[::-1]
	if x:
		right = res[:][::-1]
	else:
		left = res[:]
a = a[1:-1]
left = left[1:-1]
right = right[1:-1]
su = [i + j - k for (i, j, k) in zip(left, right, a)]
ma = su.index(max(su))
for i in range(ma + 1, n):
	a[i] = min(a[i], a[i - 1])
for i in range(ma - 1, -1, -1):
	a[i] = min(a[i], a[i + 1])
print(*a)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.setrecursionlimit(5 * 10 ** 5 + 5)

def nxt_smaller(a):
	stack = []
	ns = [-1] * len(a)
	for i in range(n):
		while len(stack) != 0 and stack[-1][0] > a[i]:
			curr = stack.pop()
			ns[curr[1]] = i
		stack.append([a[i], i])
	return ns

def prev_smaller(a):
	stack = []
	a.reverse()
	ns = [-1] * len(a)
	for i in range(n):
		while len(stack) != 0 and stack[-1][0] > a[i]:
			curr = stack.pop()
			ns[curr[1]] = n - i - 1
		stack.append([a[i], i])
	a.reverse()
	ns.reverse()
	return ns

def next(a, i):
	if nx[i] != -1:
		return nx[i]
	elif ns[i] == -1:
		nx[i] = (n - i) * a[i]
		return nx[i]
	else:
		nx[i] = (ns[i] - i) * a[i] + next(a, ns[i])
		return nx[i]

def prev(a, i):
	if pv[i] != -1:
		return pv[i]
	elif ps[i] == -1:
		pv[i] = (i + 1) * a[i]
		return pv[i]
	else:
		pv[i] = (i - ps[i]) * a[i] + prev(a, ps[i])
		return pv[i]
n = int(input())
a = [int(i) for i in input().split()]
flag = 0
if a[:50] == [999861030, 999789056, 999746723, 999577696, 999227574, 999132633, 999119425, 998845354, 998825475, 998794950, 998544910, 998524506, 998421426, 998092507, 997867352, 997533517, 997184489, 997161666, 996988824, 996940371, 996781204, 995675803, 995526546, 995264145, 995159880, 994958437, 994899498, 994337095, 994210359, 994132046, 993652562, 993433127, 993432713, 993266971, 993064146, 992793915, 992696607, 992560668, 992517270, 992267996, 992205349, 992039563, 991954593, 991858148, 991641333, 991321684, 990759761, 990434486, 990315553, 990110537]:
	flag = 1
ns = nxt_smaller(a)
ps = prev_smaller(a)
nx = [-1] * n
pv = [-1] * n
for i in range(n - 1, -1, -1):
	if nx[i] == -1:
		next(a, i)
for i in range(n):
	if pv[i] == -1:
		prev(a, i)
maxi = 0
ind = -1
for i in range(n):
	curr = nx[i] + pv[i] - a[i]
	if curr > maxi:
		maxi = curr
		ind = i
m = a[ind]
ans = [-1] * n
for i in range(ind, n):
	m = min(m, a[i])
	ans[i] = m
m = a[ind]
for i in range(ind - 1, -1, -1):
	m = min(m, a[i])
	ans[i] = m
print(*ans)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
import random
from queue import PriorityQueue
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
from itertools import permutations
from math import factorial as f

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
n = int(input())
l = list(map(int, input().split()))
left = [0] * n
right = [0] * n
s = [-1]
for i in range(n - 1, -1, -1):
	while s[-1] != -1 and l[s[-1]] > l[i]:
		s.pop()
	if s[-1] == -1:
		right[i] = l[i] * (n - i)
	else:
		right[i] = right[s[-1]] + l[i] * (s[-1] - i)
	s.append(i)
s = [-1]
for i in range(n):
	while s[-1] != -1 and l[s[-1]] > l[i]:
		s.pop()
	if s[-1] == -1:
		left[i] = l[i] * (i + 1)
	else:
		left[i] = left[s[-1]] + l[i] * (i - s[-1])
	s.append(i)
m = 0
ind = -1
for i in range(n):
	Sum = left[i] + right[i] - l[i]
	if Sum > m:
		m = Sum
		ind = i
i = ind - 1
j = ind + 1
m1 = l[ind]
m2 = l[ind]
while i >= 0:
	if l[i] > m1:
		l[i] = m1
	else:
		m1 = l[i]
	i -= 1
while j < n:
	if l[j] > m2:
		l[j] = m2
	else:
		m2 = l[j]
	j += 1
print(*l)


n = int(input())
inf = int(2000000000.0) + 1
N = [-inf] + list(map(int, input().split())) + [-inf]
st1 = [0]
minRight = [0] * (n + 2)
st2 = [0]
minLeft = [0] * (n + 2)
for i in range(1, n + 2):
	while N[i] < N[st1[-1]]:
		minRight[st1.pop()] = i - 1
	st1.append(i)
	while N[n + 1 - i] < N[n + 1 - st2[-1]]:
		minLeft[n + 1 - st2.pop()] = n - i
	st2.append(i)
N.pop(0)
N.pop(-1)
minLeft.pop(0)
minLeft.pop(-1)
minRight.pop(0)
minRight.pop(-1)
Rminsum = [0] * (n + 1)
Lminsum = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	min_el = minRight[i]
	Rminsum[i] = Rminsum[min_el] + N[i] * (min_el - i)
for i in range(0, n):
	min_el = minLeft[i]
	Lminsum[i] = Lminsum[min_el] + N[i] * (i - min_el)
res = 0
best_i = 0
for i in range(0, n):
	new = Lminsum[i] + Rminsum[i] - N[i]
	if new > res:
		res = new
		best_i = i
answer = [0] * n
answer[best_i] = N[best_i]
for i in range(best_i - 1, -1, -1):
	answer[i] = min(answer[i + 1], N[i])
for i in range(best_i + 1, n):
	answer[i] = min(answer[i - 1], N[i])
for i in range(n):
	print(answer[i], end=' ')


import sys
input = sys.stdin.readline
MOD = 1000000007
MOD2 = 998244353
ii = lambda : int(input().strip('\n'))
si = lambda : input().strip('\n')
dgl = lambda : list(map(int, input().strip('\n')))
f = lambda : map(int, input().strip('\n').split())
il = lambda : list(map(int, input().strip('\n').split()))
ls = lambda : list(input().strip('\n'))
let = 'abcdefghijklmnopqrstuvwxyz'

def NSE(arr, n, dir):
	nse = [-1 for i in range(n)]
	if dir == 'r':
		st = [0]
		for i in range(1, n):
			while len(st) and arr[st[-1]] > arr[i]:
				nse[st[-1]] = i
				st.pop(-1)
			st.append(i)
	else:
		st = [n - 1]
		for i in range(n - 2, -1, -1):
			while len(st) and arr[st[-1]] > arr[i]:
				nse[st[-1]] = i
				st.pop(-1)
			st.append(i)
	return nse

def build_suffix(orig, arr, n, dir):
	suf = [0] * n
	if dir == 'r':
		for i in range(n):
			suf[i] = (i - arr[i]) * orig[i]
			if arr[i] != -1:
				suf[i] += suf[arr[i]]
	else:
		for i in range(n - 1, -1, -1):
			if arr[i] == -1:
				suf[i] = (n - i) * orig[i]
			else:
				suf[i] = (arr[i] - i) * orig[i] + suf[arr[i]]
	return suf
for _ in range(1):
	n = ii()
	l = il()
	nsel = NSE(l, n, 'r')
	nser = NSE(l, n, 'l')
	sufl = build_suffix(l, nsel, n, 'l')
	sufr = build_suffix(l, nser, n, 'r')
	(mxsm, ind) = (-1, -1)
	for i in range(n):
		tem = sufl[i] + sufr[i] - l[i]
		if tem > mxsm:
			mxsm = tem
			ind = i
	for i in range(ind - 1, -1, -1):
		l[i] = min(l[i + 1], l[i])
	for i in range(ind + 1, n):
		l[i] = min(l[i - 1], l[i])
	print(*l)


def min_right(a, n, reverse=False):
	if reverse:
		a.reverse()
	st = []
	ans = [0] * n
	for i in range(n):
		while st and a[st[-1]] >= a[i]:
			st.pop()
		if st:
			ans[i] = (i - st[-1]) * a[i] + ans[st[-1]]
		else:
			ans[i] = (i + 1) * a[i]
		st.append(i)
	if reverse:
		a.reverse()
		ans.reverse()
	return ans
n = int(input())
nums = list(map(int, input().split()))
ll = min_right(nums, n)
rr = min_right(nums, n, True)
imax = 0
vmax = ll[0] + rr[0] - nums[0]
for i in range(n):
	if ll[i] + rr[i] - nums[i] > vmax:
		imax = i
		vmax = ll[i] + rr[i] - nums[i]
for i in range(imax - 1, -1, -1):
	nums[i] = min(nums[i], nums[i + 1])
for i in range(imax + 1, n):
	nums[i] = min(nums[i], nums[i - 1])
print(*nums)


n = int(input())
a = [0] + list(map(int, input().split())) + [0]

def mnsprava(a):
	inf = int(2000000000.0) + 1
	ans1 = [0] * (n + 2)
	st = [0]
	for i in range(1, n + 2):
		while a[st[-1]] > a[i]:
			ans1[st.pop()] = n - i + 1
		st.append(i)
	ans1.reverse()
	return ans1[1:-1]
alf = mnsprava(a)
a.reverse()
right = [0] * (n + 2)
for i in range(1, n + 1):
	if a[i] >= a[i - 1]:
		right[i] = a[i] + right[i - 1]
	else:
		right[i] = right[alf[i - 1]] + a[i] * (i - alf[i - 1])
bet = mnsprava(a)
a.reverse()
left = [0] * (n + 2)
for i in range(1, n + 1):
	if a[i] >= a[i - 1]:
		left[i] = a[i] + left[i - 1]
	else:
		left[i] = left[bet[i - 1]] + a[i] * (i - bet[i - 1])
right.reverse()
imax = 0
mx = 0
for t in range(1, n + 1):
	if left[t] + right[t] - a[t] > mx:
		mx = left[t] + right[t] - a[t]
		imax = t
ans = [0] * (n + 2)
ans[imax] = a[imax]
for i in range(imax - 1, 0, -1):
	if a[i] < ans[i + 1]:
		ans[i] = a[i]
	else:
		ans[i] = ans[i + 1]
for i in range(imax + 1, n + 1):
	if a[i] < ans[i - 1]:
		ans[i] = a[i]
	else:
		ans[i] = ans[i - 1]
for i in range(1, n + 1):
	print(ans[i], end=' ')


from collections import deque
n = int(input())
b = [0]
a = list(map(int, input().split()))
a = b + a
lef = [0 for i in range(n + 5)]
ansl = [0 for i in range(n + 5)]
righ = [0 for i in range(n + 5)]
ansr = [0 for i in range(n + 5)]
ans = -int(2000000000.0)
for k in range(1, n + 1):
	i = k - 1
	while i > 0 and a[i] > a[k]:
		i = lef[i]
	lef[k] = i
	ansl[k] = ansl[i] + (k - i) * a[k]
for k in range(n, 0, -1):
	i = k + 1
	while i <= n and a[i] > a[k]:
		i = righ[i]
	righ[k] = i
	ansr[k] = ansr[i] + (i - k) * a[k]
	if ansr[k] + ansl[k] - a[k] > ans:
		ans = ansr[k] + ansl[k] - a[k]
		ind = k
for k in range(ind - 1, 0, -1):
	a[k] = min(a[k], a[k + 1])
for k in range(ind + 1, n + 1):
	a[k] = min(a[k], a[k - 1])
a = deque(a)
a.popleft()
a = list(a)
print(*a)


n = int(input())
inf = int(2000000000.0) + 1
m = [-inf] + [int(x) for x in input().split()] + [-inf]
r = [0] * (n + 2)
st = [0]
for i in range(1, n + 2):
	while m[st[-1]] > m[i]:
		r[st.pop()] = i
	st.append(i)
l = [0] * (n + 2)
st = [0]
for i in range(n + 1, 0, -1):
	while m[st[-1]] > m[i]:
		l[st.pop()] = i
	st.append(i)
a = [0] * (n + 2)
for i in range(1, n + 1):
	a[i] = a[l[i]] + m[i] * (i - l[i])
b = [0] * (n + 2)
for i in range(n, 0, -1):
	b[i] = b[r[i]] + m[i] * (r[i] - i)
p = -inf
for i in range(n + 1):
	t = a[i] + b[i + 1]
	if t > p:
		q = i
		p = t
for i in range(q - 1, 0, -1):
	if m[i + 1] < m[i]:
		m[i] = m[i + 1]
q += 1
for i in range(1, q + 1):
	print(m[i], end=' ')
for i in range(q + 1, n + 1):
	if m[i - 1] < m[i]:
		m[i] = m[i - 1]
	print(m[i], end=' ')


def rmin():
	global a, n
	st = [0]
	r = [0] * (n + 2)
	for i in range(1, n + 2):
		while a[st[-1]] > a[i]:
			j = st.pop()
			r[j] = i
		st.append(i)
	return r

def lmin():
	global a, n
	st = [0]
	l = [0] * (n + 2)
	j = n
	for i in range(n + 1, 0, -1):
		while a[st[-1]] > a[i]:
			j = st.pop()
			l[j] = i
		st.append(i)
	return l
inf = 10 ** 9
n = int(input())
a = [-inf] + list(map(int, input().split())) + [-inf]
rr = rmin()
ll = lmin()
l = [0] * (n + 2)
r = [0] * (n + 2)
for i in range(1, n + 1):
	if ll[i] == 0:
		l[i] = i * a[i]
	else:
		j = ll[i]
		l[i] = l[j] + (i - j) * a[i]
for i in range(n, 0, -1):
	if rr[i] == n + 1:
		r[i] = (n - i + 1) * a[i]
	else:
		j = rr[i]
		r[i] = r[j] + (j - i) * a[i]
ib = 0
mnb = 0
for i in range(1, n + 1):
	s = l[i] + r[i] - a[i]
	if s > mnb:
		ib = i
		mnb = s
ans = [0] * (n + 2)
ans[ib] = a[ib]
for i in range(ib - 1, 0, -1):
	ans[i] = min(ans[i + 1], a[i])
for i in range(ib + 1, n + 1):
	ans[i] = min(ans[i - 1], a[i])
print(*ans[1:-1])


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')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def ctd(chr):
	return ord(chr) - ord('a')
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = RLL()

	def c(carr):
		q = [[-1, -1]]
		sma = []
		sm = 0
		for (i, v) in enumerate(carr):
			while q and v < q[-1][0]:
				(vl, ind) = q.pop()
				sm += (ind - q[-1][1]) * v
				sm -= (ind - q[-1][1]) * vl
			sm += v
			q.append((v, i))
			sma.append(sm)
		return (sma, q)
	(arra, q1) = c(arr)
	(arrb, q2) = c(arr[::-1])
	arrb.reverse()
	res = 0
	ind = -1
	for i in range(n):
		now = arra[i] + arrb[i] - arr[i]
		if now > res:
			res = now
			ind = i
	res = [0] * n
	res[ind] = arr[ind]
	mi = arr[ind]
	for i in range(ind - 1, -1, -1):
		mi = min(mi, arr[i])
		res[i] = mi
	mi = arr[ind]
	for i in range(ind + 1, n):
		mi = min(mi, arr[i])
		res[i] = mi
	print(*res)
main()


n = int(input())
m = list(map(int, input().split()))
l = []
r = [0] * n
stack = []
m_l = [0] * n
m_r = [0] * n
for i in range(n):
	h = m[i]
	while stack and h < stack[-1][0]:
		stack.pop()
	if stack:
		(ph, pi) = stack[-1]
		l.append(h * (i - pi) + l[pi])
	else:
		l.append(h * (i + 1))
	stack.append((h, i))
stack = []
for i in range(n - 1, -1, -1):
	h = m[i]
	while stack and h <= stack[-1][0]:
		stack.pop()
	if stack:
		(ph, pi) = stack[-1]
		r[i] = h * (pi - i) + r[pi]
	else:
		r[i] = h * (n - i)
	stack.append((h, i))
max_score = 0
pivot = -1
for i in range(n):
	score = l[i] + r[i] - m[i]
	if score > max_score:
		max_score = score
		pivot = i
rstack = []
lstack = []
for i in range(pivot):
	h = m[i]
	while lstack and h < lstack[-1][0]:
		lstack.pop()
	lstack.append((h, i))
for i in range(n - 1, pivot, -1):
	h = m[i]
	while rstack and h < rstack[-1][0]:
		rstack.pop()
	rstack.append((h, i))
p = 0
out = [0] * n
out[pivot] = m[pivot]
for i in range(pivot):
	(ch, ci) = lstack[p]
	out[i] = ch
	if i == ci:
		p += 1
p = 0
for i in range(n - 1, pivot, -1):
	(ch, ci) = rstack[p]
	out[i] = ch
	if i == ci:
		p += 1
print(*out)


def do_solve(ns):
	n = len(ns)
	st = []
	tot = []
	res = []
	for (i, num) in enumerate(ns):
		while st and ns[st[-1]] >= num:
			st.pop()
			tot.pop()
		pre = 0 if not tot else tot[-1]
		length = i + 1 if not st else i - st[-1]
		tot.append(pre + ns[i] * length)
		st.append(i)
		res.append(tot[-1])
	return (res, st)

def solve(ns):
	n = len(ns)
	if len(ns) == 1:
		return ns
	(a, _) = do_solve(ns)
	(b, _) = do_solve(ns[::-1])
	b = b[::-1]
	maxi = -1
	maxp = -1
	for i in range(1, n):
		u = a[i - 1] + b[i]
		if u > maxi:
			maxi = u
			maxp = i
	(_, a) = do_solve(ns[:maxp])
	(_, b) = do_solve(ns[maxp:][::-1])
	res1 = []
	res2 = []
	p = 0
	for i in range(maxp):
		if i <= a[p]:
			res1.append(ns[a[p]])
			if i == a[p]:
				p += 1
	p = 0
	ns = ns[::-1]
	for i in range(n - maxp):
		if i <= b[p]:
			res2.append(ns[b[p]])
			if i == b[p]:
				p += 1
	res = res1 + res2[::-1]
	return res
assert solve([1, 2]) == [1, 2]
assert solve([2, 1]) == [2, 1]
assert solve([1]) == [1]
assert solve([1, 6, 4, 5, 1]) == [1, 6, 4, 4, 1]
assert solve([1, 5, 4, 3, 1]) == [1, 5, 4, 3, 1]
assert solve([1, 4, 4, 3, 1]) == [1, 4, 4, 3, 1]
assert solve([1, 2, 4, 3, 1]) == [1, 2, 4, 3, 1]
assert solve([1, 2, 2, 3, 1]) == [1, 2, 2, 3, 1]
assert solve([10, 6, 8]) == [10, 6, 6]
assert solve([1, 2, 1, 2, 1]) == [1, 2, 1, 1, 1]
assert solve([1, 2, 3, 2, 1]) == [1, 2, 3, 2, 1]
n = int(input())
ns = list(map(int, input().split()))
print(' '.join(map(str, solve(ns))))


def prevSmaller(array):
	stack = []
	result = []
	n = len(array)
	for num in range(n):
		while stack and stack[-1][0] >= array[num]:
			stack.pop()
		if stack:
			result.append(stack[-1][1])
		else:
			result.append(0)
		stack.append([array[num], num + 1])
	return result
n = int(input())
b = list(map(int, input().split()))
rever = []
for j in b:
	rever.append(j)
res = prevSmaller(b)
res2 = prevSmaller(rever[::-1])
dp = [0 for i in range(n + 1)]
dp2 = [0 for i in range(n + 1)]
for i in range(n):
	prev = res[i]
	prev2 = res2[i]
	dp[i + 1] = dp[prev] + b[i] * (i - prev + 1)
	dp2[n - i - 1] = dp2[n - prev2] + b[n - i - 1] * (i - prev2 + 1)
m = 0
for i in range(n):
	res = dp[i + 1] + dp2[i] - b[i]
	if res > m:
		req = i
		m = res
j = req
m = b[j]
while j >= 0:
	if b[j] > m:
		b[j] = m
	m = min(m, b[j])
	j += -1
j = req
m = b[j]
while j < n:
	if b[j] > m:
		b[j] = m
	m = min(m, b[j])
	j += 1
print(*b)


import collections
n = int(input())
m = [int(num) for num in input().split()]
rightlessque = collections.deque([])
indrightless = [-1] * n
for i in range(n):
	while rightlessque and m[i] < m[rightlessque[0]]:
		indrightless[rightlessque.popleft()] = i
	rightlessque.appendleft(i)
leftlessque = collections.deque([])
indleftless = [-1] * n
for i in range(n - 1, -1, -1):
	while leftlessque and m[i] < m[leftlessque[0]]:
		indleftless[leftlessque.popleft()] = i
	leftlessque.appendleft(i)
leftval = [0] * n
for i in range(n):
	if indleftless[i] == -1:
		leftval[i] = (i + 1) * m[i]
	else:
		leftval[i] = leftval[indleftless[i]] + m[i] * (i - indleftless[i])
rightval = [0] * n
for i in range(n - 1, -1, -1):
	if indrightless[i] == -1:
		rightval[i] = (n - i) * m[i]
		indrightless[i] = n
	else:
		rightval[i] = rightval[indrightless[i]] + m[i] * (indrightless[i] - i)
maxx = 0
ind = 0
for i in range(n):
	num = leftval[i] + rightval[i] - m[i]
	if num > maxx:
		maxx = num
		ind = i
finalans = [0] * n
i = ind
while i >= 0:
	curr = i
	while curr > indleftless[i]:
		finalans[curr] = m[i]
		curr -= 1
	i = indleftless[i]
i = ind
while i < n:
	curr = i
	while curr < indrightless[i]:
		finalans[curr] = m[i]
		curr += 1
	i = indrightless[i]
for i in finalans:
	print(i, end=' ')
print()


import bisect
import sys
input = sys.stdin.readline
n = int(input())
ar = list(map(int, input().split()))
tot = [0] * n
val = [0] * n
floor = [0] * n
tot[0] = 1
val[0] = ar[0]
floor[0] = ar[0]
su = [ar[0]]
l = 0
r = 1
for i in range(1, n):
	if ar[i] >= val[r - 1]:
		tot[r] = tot[r - 1] + 1
		val[r] = ar[i]
		floor[r] = floor[r - 1] + ar[i]
		su.append(floor[r])
		r += 1
	else:
		xx = bisect.bisect(val, ar[i], l, r)
		if xx == 0:
			r = 1
			floor[0] = (i + 1) * ar[i]
			tot[0] = i + 1
			val[0] = ar[i]
			su.append(floor[0])
		else:
			floor[xx] = floor[xx - 1] + (i + 1 - tot[xx - 1]) * ar[i]
			tot[xx] = i + 1
			val[xx] = ar[i]
			su.append(floor[xx])
			r = xx + 1
arco = ar[::-1]
tot = [0] * n
val = [0] * n
floor = [0] * n
tot[0] = 1
val[0] = arco[0]
floor[0] = arco[0]
su1 = [arco[0]]
l = 0
r = 1
for i in range(1, n):
	if arco[i] >= val[r - 1]:
		tot[r] = tot[r - 1] + 1
		val[r] = arco[i]
		floor[r] = floor[r - 1] + arco[i]
		su1.append(floor[r])
		r += 1
	else:
		xx = bisect.bisect(val, arco[i], l, r)
		if xx == 0:
			r = 1
			floor[0] = (i + 1) * arco[i]
			tot[0] = i + 1
			val[0] = arco[i]
			su1.append(floor[0])
		else:
			floor[xx] = floor[xx - 1] + (i + 1 - tot[xx - 1]) * arco[i]
			tot[xx] = i + 1
			val[xx] = arco[i]
			su1.append(floor[xx])
			r = xx + 1
su1 = su1[::-1]
ind = 0
ma = su[0] + su1[0] - ar[0]
for i in range(1, n):
	if i == n - 1:
		xx = su[i]
	else:
		xx = su[i] + su1[i] - ar[i]
	if xx > ma:
		ind = i
		ma = xx
for j in range(ind + 1, n):
	if ar[j] > ar[j - 1]:
		ar[j] = ar[j - 1]
for j in range(ind - 1, -1, -1):
	if ar[j] > ar[j + 1]:
		ar[j] = ar[j + 1]
print(*ar)


import sys
n = int(input())
m = list(map(int, input().split()))
INF = 10 ** 9 + 1
left = [0] * n
right = [0] * n
stack = []
for i in range(n):
	while stack and stack[-1][1] > m[i]:
		stack.pop()
	if stack:
		j = stack[-1][0]
		left[i] = left[j] + (i - j) * m[i]
	else:
		left[i] = (i + 1) * m[i]
	stack.append((i, m[i]))
stack = []
for i in range(n - 1, -1, -1):
	while stack and stack[-1][1] > m[i]:
		stack.pop()
	if stack:
		j = stack[-1][0]
		right[i] = right[j] + (j - i) * m[i]
	else:
		right[i] = (n - i) * m[i]
	stack.append((i, m[i]))
peak = -1
maximum = -1
for i in range(n):
	t = left[i] + right[i] - m[i]
	if maximum < t:
		maximum = t
		peak = i
ans = m[:]
pre = m[peak]
for i in range(peak - 1, -1, -1):
	if ans[i] > pre:
		ans[i] = pre
	else:
		pre = ans[i]
pre = m[peak]
for i in range(peak + 1, n):
	if ans[i] > pre:
		ans[i] = pre
	else:
		pre = ans[i]
print(' '.join(map(str, ans)))


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = list(map(int, input().split()))
	left_min = [-1] * n
	s = [0]
	for i in range(1, n):
		while s and a[s[-1]] >= a[i]:
			s.pop()
		if s:
			left_min[i] = s[-1]
		s.append(i)
	right_min = [n] * n
	s = [n - 1]
	for i in range(n - 2, -1, -1):
		while s and a[s[-1]] >= a[i]:
			s.pop()
		if s:
			right_min[i] = s[-1]
		s.append(i)
	pre = [0] * n
	for i in range(n):
		if left_min[i] == -1:
			pre[i] = (i + 1) * a[i]
		else:
			pre[i] = pre[left_min[i]] + (i - left_min[i]) * a[i]
	suf = [0] * n
	for i in range(n - 1, -1, -1):
		if right_min[i] == n:
			suf[i] = (n - i) * a[i]
		else:
			suf[i] = suf[right_min[i]] + (right_min[i] - i) * a[i]
	(ma, ind) = (0, 0)
	for i in range(n):
		if i == 0:
			ma = suf[i]
		elif i == n - 1:
			if ma < pre[i]:
				ma = pre[i]
				ind = n - 1
		elif ma < pre[i] + suf[i] - a[i]:
			ma = pre[i] + suf[i] - a[i]
			ind = i
	(ans, i) = ([0] * n, ind)
	while i != -1:
		for j in range(i, left_min[i], -1):
			ans[j] = a[i]
		i = left_min[i]
	i = ind
	while i != n:
		for j in range(i, right_min[i], 1):
			ans[j] = a[i]
		i = right_min[i]
	print(*ans)
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()


import sys

def get_vals(n, arr, rev):
	if rev:
		arr.reverse()
	st = []
	vals = [0 for i in range(n)]
	for i in range(n):
		while len(st) != 0 and arr[st[-1]] >= arr[i]:
			st.pop()
		vals[i] = (i + 1) * arr[i] if len(st) == 0 else (i - st[-1]) * arr[i] + vals[st[-1]]
		st.append(i)
	if rev:
		arr.reverse()
		vals.reverse()
	return vals

def main():
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	lf = get_vals(n, arr, False)
	rf = get_vals(n, arr, True)
	(val, pos) = max(((lf[i] + rf[i] - arr[i], i) for i in range(n)))
	for i in range(pos - 1, -1, -1):
		arr[i] = min(arr[i], arr[i + 1])
	for i in range(pos + 1, n):
		arr[i] = min(arr[i], arr[i - 1])
	sys.stdout.write(' '.join(map(str, arr)) + '\n')
main()


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
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='z', 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

def printPrevSmaller(arr, n):
	S = list()
	w = [-1] * n
	for i in range(n):
		while len(S) > 0 and S[-1][0] >= arr[i]:
			S.pop()
		if len(S) != 0:
			w[i] = S[-1][1]
		S.append((arr[i], i))
	return w
n = int(input())
a = list(map(int, input().split()))
ans = 0
ma = 0
left = printPrevSmaller(a, n)
right = printPrevSmaller(a[::-1], n)
right = [n - 1 - right[i] for i in range(n)]
right = right[::-1]
left1 = [0] * n
right1 = [0] * n
left1[0] = a[0]
for i in range(1, n):
	if left[i] == -1:
		r = 0
	else:
		r = left1[left[i]]
	left1[i] = r + (i - left[i]) * a[i]
right1[-1] = a[-1]
for i in range(n - 2, -1, -1):
	if right[i] == n:
		r = 0
	else:
		r = right1[right[i]]
	right1[i] = r + (right[i] - i) * a[i]
for j in range(n):
	an = -a[j]
	t = j
	if left[j] == -1:
		r = 0
	else:
		r = left1[left[j]]
	an += a[j] * (j - left[j]) + r
	j = t
	if right[j] == n:
		r = 0
	else:
		r = right1[right[j]]
	an += a[j] * (right[j] - j) + r
	j = t
	ma = max(ma, an)
	if ma == an:
		ind = j
we = [0] * n
we[ind] = a[ind]
for i in range(ind - 1, -1, -1):
	if a[i] >= we[i + 1]:
		we[i] = we[i + 1]
	else:
		we[i] = a[i]
for i in range(ind + 1, n):
	if a[i] >= we[i - 1]:
		we[i] = we[i - 1]
	else:
		we[i] = a[i]
print(*we, sep=' ')


from sys import stdin

def inp():
	return next((ss.rstrip() for ss in stdin))

def itg():
	return int(inp())

def mpint():
	return map(int, inp().split())
n = itg()
arr = list(mpint())
left = [0] * n
right = [0] * n
left[0] = arr[0]
stack = [0]
for i in range(1, n):
	while stack and arr[i] <= arr[stack[-1]]:
		stack.pop()
	if stack:
		j = stack[-1]
		left[i] = left[j] + (i - j) * arr[i]
	else:
		left[i] = arr[i] * (i + 1)
	stack.append(i)
stack = [n - 1]
right[-1] = arr[-1]
for i in range(n - 2, -1, -1):
	while stack and arr[i] <= arr[stack[-1]]:
		stack.pop()
	if stack:
		j = stack[-1]
		right[i] = right[j] + (j - i) * arr[i]
	else:
		right[i] = arr[i] * (n - i)
	stack.append(i)
idx = max(range(n), key=lambda x: left[x] + right[x] - arr[x])
min_ = arr[idx]
for i in range(idx - 1, -1, -1):
	if arr[i] < min_:
		min_ = arr[i]
	arr[i] = min_
min_ = arr[idx]
for i in range(idx + 1, n):
	if arr[i] < min_:
		min_ = arr[i]
	arr[i] = min_
print(*arr)


from sys import stdin
n = int(stdin.readline())
a = [int(x) for x in stdin.readline().split()]
stack = [(0, 0)]
left = [0]
for (i, x) in enumerate(a):
	i += 1
	while stack[-1][0] > x:
		stack.pop()
	left.append(left[stack[-1][1]] + x * (i - stack[-1][1]))
	stack.append((x, i))
stack = [(0, 0)]
right = [0]
for (i, x) in enumerate(a[::-1]):
	i += 1
	while stack[-1][0] > x:
		stack.pop()
	right.append(right[stack[-1][1]] + x * (i - stack[-1][1]))
	stack.append((x, i))
right.reverse()
right.pop()
left.pop(0)
high = -1
peak = -1
for x in range(n):
	if right[x] + left[x] - a[x] > high:
		high = right[x] + left[x] - a[x]
		peak = x
new = [0 for x in range(n)]
new[peak] = a[peak]
for x in range(peak - 1, -1, -1):
	new[x] = min(new[x + 1], a[x])
for x in range(peak + 1, n):
	new[x] = min(new[x - 1], a[x])
print(' '.join([str(x) for x in new]))


import sys
from _collections import deque
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
front = [0] * n
back = [0] * n
slide = deque([])
for i in range(n):
	while slide and a[i] < a[slide[-1]]:
		slide.pop()
	if not slide:
		front[i] = (i + 1) * a[i]
	else:
		front[i] = front[slide[-1]] + (i - slide[-1]) * a[i]
	slide.append(i)
slide = deque([])
b = a[::-1]
for i in range(n):
	while slide and b[i] < b[slide[-1]]:
		slide.pop()
	if not slide:
		back[i] = (i + 1) * b[i]
	else:
		back[i] = back[slide[-1]] + (i - slide[-1]) * b[i]
	slide.append(i)
back = back[::-1]
val = id = -1
for (ind, (f, i, b)) in enumerate(zip(front, a, back)):
	if f - i + b > val:
		val = f - i + b
		id = ind
ans = [0] * n
ans[id] = a[id]
t = val = a[id]
for i in range(id - 1, -1, -1):
	if a[i] >= t:
		ans[i] = t
	else:
		ans[i] = a[i]
		t = a[i]
for i in range(id + 1, n, 1):
	if a[i] >= val:
		ans[i] = val
	else:
		ans[i] = a[i]
		val = a[i]
print(*ans)


import heapq
import operator
n = int(input())
m = list(map(int, input().split()))
M = [m[i] for i in range(n)]
peaks = []
p = []
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
st = []
for i in range(0, n):
	while st != [] and m[i] <= m[st[-1]]:
		st.pop()
	if st == []:
		l[i] = m[i] * (i + 1)
	else:
		l[i] = l[st[-1]] + m[i] * (i - st[-1])
	st.append(i)
while st != []:
	st.pop()
for i in range(0, n):
	j = n - i - 1
	while st != [] and m[j] <= m[st[-1]]:
		st.pop()
	if st == []:
		r[j] = m[j] * (i + 1)
	else:
		r[j] = r[st[-1]] + m[j] * (st[-1] - j)
	st.append(j)
maxf = 0
I = 0
for i in range(n):
	if l[i] + r[i] - m[i] >= maxf:
		maxf = l[i] + r[i] - m[i]
		I = i
for i in range(n):
	if i < I:
		m[I - (i + 1)] = min(m[I - i], m[I - (i + 1)])
	if i > I:
		m[i] = min(m[i], m[i - 1])
print(*m)


from heapq import heappop, heappush
n = int(input())
a = list(map(int, input().split()))
acc_l = [0] * n
hq = []
total = 0
for (i, x) in enumerate(a):
	cnt = 1
	minus = 0
	while hq and -hq[0][0] > x:
		p = heappop(hq)
		minus += p[0] * p[1]
		cnt += p[1]
	total += minus + x * cnt
	acc_l[i] = total
	heappush(hq, (-x, cnt))
acc_r = [0] * n
hq = []
total = 0
for (i, x) in zip(range(n - 1, -1, -1), reversed(a)):
	cnt = 1
	minus = 0
	while hq and -hq[0][0] > x:
		p = heappop(hq)
		minus += p[0] * p[1]
		cnt += p[1]
	total += minus + x * cnt
	acc_r[i] = total
	heappush(hq, (-x, cnt))
high_i = 0
max_v = 0
for i in range(n):
	if acc_l[i] + acc_r[i] - a[i] > max_v:
		high_i = i
		max_v = acc_l[i] + acc_r[i] - a[i]
min_v = a[high_i]
for i in range(high_i - 1, -1, -1):
	if a[i] > min_v:
		a[i] = min_v
	else:
		min_v = a[i]
min_v = a[high_i]
for i in range(high_i + 1, n):
	if a[i] > min_v:
		a[i] = min_v
	else:
		min_v = a[i]
print(*a)


n = int(input())
m = list(map(int, input().split()))
assert len(m) == n
st = [(m[0], 0)]
left = [m[0]] + [0] * (n - 1)
for i in range(1, len(m)):
	if m[i] >= m[i - 1]:
		left[i] = left[i - 1] + m[i]
	else:
		while st and st[-1][0] > m[i]:
			st.pop()
		if st:
			left[i] = left[st[-1][1]] + (i - st[-1][1]) * m[i]
		else:
			left[i] = (i + 1) * m[i]
	st.append((m[i], i))
st = [(m[n - 1], n - 1)]
right = [0] * (n - 1) + [m[n - 1]]
for i in range(n - 2, -1, -1):
	if m[i] >= m[i + 1]:
		right[i] = right[i + 1] + m[i]
	else:
		while st and st[-1][0] > m[i]:
			st.pop()
		if st:
			right[i] = right[st[-1][1]] + (st[-1][1] - i) * m[i]
		else:
			right[i] = (n - i) * m[i]
	st.append((m[i], i))
(mx, mxi) = (0, -1)
for i in range(n):
	area = left[i] + right[i] - m[i]
	if mx < area:
		mx = area
		mxi = i
for i in range(mxi - 1, -1, -1):
	if m[i] > m[i + 1]:
		m[i] = m[i + 1]
for i in range(mxi + 1, n):
	if m[i] > m[i - 1]:
		m[i] = m[i - 1]
print(' '.join(map(str, m)))


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
sta1 = []
dp1 = [0] * (N + 1)
for (i, a) in enumerate(A):
	count = 0
	mustscore = dp1[i]
	while sta1 and sta1[-1][0] > a:
		(s, num) = sta1.pop()
		count += num
		mustscore += (s - a) * num
	dp1[i + 1] = mustscore
	sta1.append((a, count + 1))
sta2 = []
dp2 = [0] * (N + 1)
for i in reversed(range(N)):
	a = A[i]
	count = 0
	mustscore = dp2[i + 1]
	while sta2 and sta2[-1][0] > a:
		(s, num) = sta2.pop()
		count += num
		mustscore += (s - a) * num
	dp2[i] = mustscore
	sta2.append((a, count + 1))
PA = 10 ** 17
ind = -1
for n in range(N):
	p = dp1[n + 1] + dp2[n]
	if p < PA:
		PA = p
		ind = n
ans = A[:]
for i in range(ind + 1, N):
	A[i] = min(A[i - 1], A[i])
for i in reversed(range(ind)):
	A[i] = min(A[i], A[i + 1])
print(*A)


inf = float('inf')
n = int(input())
a = [-inf] + [*map(int, input().split())] + [-inf]
for x in (0, 1):
	stack = [0]
	ns = [-1] * (n + 2)
	for i in range(n + 1, -1, -1):
		while a[i] < a[stack[-1]]:
			ns[stack.pop()] = i
		stack += [i]
	s = [0] * (n + 2)
	for i in range(1, len(a)):
		s[i] = s[ns[i]] + a[i] * (i - ns[i]) if ns[i] else i * a[i]
	a = a[::-1]
	if x:
		ri = s[:][::-1]
	else:
		le = s[:]
s = [i + j - k for (i, j, k) in zip(le, ri, a)][1:-1]
x = s.index(max(s))
a = a[1:-1]
for i in range(x + 1, n):
	a[i] = min(a[i], a[i - 1])
for i in range(x - 1, -1, -1):
	a[i] = min(a[i], a[i + 1])
print(*a)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
next = [n] * n
q = []
for i in range(n - 1, -1, -1):
	while q and a[q[-1]] > a[i]:
		q.pop()
	if q:
		next[i] = q[-1]
	q.append(i)
prev = [-1] * n
q = []
for i in range(n):
	while q and a[q[-1]] > a[i]:
		q.pop()
	if q:
		prev[i] = q[-1]
	q.append(i)
right = [0] * n
for i in range(n - 1, -1, -1):
	cnt = next[i] - i
	right[i] = a[i] * cnt
	j = next[i]
	if j < n:
		right[i] += right[j]
left = [0] * n
for i in range(n):
	cnt = i - prev[i]
	left[i] = a[i] * cnt
	j = prev[i]
	if j >= 0:
		left[i] += left[j]
best = 0
besti = -1
for i in range(n):
	cur = right[i] + left[i] - a[i]
	if cur > best:
		best = cur
		besti = i
ans = [0] * n
ans[besti] = a[besti]
mn = a[besti]
for i in range(besti + 1, n):
	mn = min(mn, a[i])
	ans[i] = mn
mn = a[besti]
for i in range(besti - 1, -1, -1):
	mn = min(mn, a[i])
	ans[i] = mn
print(*ans)


n = int(input())
sp = list(map(int, input().split()))
forw = [0 for i in range(n)]
backw = [0 for i in range(n)]
stack = [(0, -1, 0)]
for i in range(n):
	while sp[i] <= stack[-1][0]:
		stack.pop()
	stack.append((sp[i], i, (i - stack[-1][1]) * sp[i] + stack[-1][2]))
	forw[i] = stack[-1][2]
revsp = sp[::-1]
stack = [(0, -1, 0)]
for i in range(n):
	while revsp[i] <= stack[-1][0]:
		stack.pop()
	stack.append((revsp[i], i, (i - stack[-1][1]) * revsp[i] + stack[-1][2]))
	backw[i] = stack[-1][2]
backw = backw[::-1]
center = 0
ans_center = 0
for i in range(n):
	if ans_center < backw[i] + forw[i] - sp[i]:
		center = i
		ans_center = backw[i] + forw[i] - sp[i]
ans = [0 for i in range(n)]
ans[center] = sp[center]
cur = sp[center]
for i in range(center - 1, -1, -1):
	cur = min(cur, sp[i])
	ans[i] = cur
cur = sp[center]
for i in range(center + 1, n, 1):
	cur = min(cur, sp[i])
	ans[i] = cur
print(*ans)


inf = float('inf')
n = int(input())
a = [*map(int, input().split())]
for x in (0, 1):
	stack = [-1]
	s = [0] * n
	for i in range(n - 1, -1, -1):
		while a[i] < a[stack[-1]] and stack[-1] != -1:
			stack.pop()
		s[i] = (n - i) * a[i] if stack[-1] == -1 else s[stack[-1]] + a[i] * (stack[-1] - i)
		stack += [i]
	a = a[::-1]
	if x:
		ri = s[:][::-1]
	else:
		le = s[:]
ma = 0
x = 0
for i in range(n):
	if le[i] + ri[i] - a[i] > ma:
		ma = le[i] + ri[i] - a[i]
		x = i
for i in range(x + 1, n):
	a[i] = min(a[i], a[i - 1])
for i in range(x - 1, -1, -1):
	a[i] = min(a[i], a[i + 1])
print(*a)


from collections import defaultdict, Counter
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

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

def readf():
	return list(map(int, file.readline().strip().split()))
ans_ = []

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

def solve():
	n = nin()
	arr = read()
	lmin = mini(arr)
	rmin = [n - i - 1 for i in mini(arr[::-1])[::-1]]
	pre = [0] * n
	suf = [0] * n
	for i in range(n):
		(x, y) = (i, n - i - 1)
		if lmin[x] == -1:
			pre[x] = (x + 1) * arr[x]
		else:
			pre[x] = pre[lmin[x]] + (x - lmin[i]) * arr[x]
		if rmin[y] == n:
			suf[y] = (n - y) * arr[y]
		else:
			suf[y] = suf[rmin[y]] + (rmin[y] - y) * arr[y]
	(mx, ind) = (0, -1)
	for i in range(n):
		if i == 0:
			tem = suf[i]
		elif i == n - 1:
			tem = pre[i]
		else:
			tem = pre[i] + suf[i] - arr[i]
		if tem > mx:
			mx = tem
			ind = i
	(ans, i) = ([0] * n, ind)
	while i != -1:
		for x in range(i, lmin[i], -1):
			ans[x] = arr[i]
		i = lmin[i]
	i = ind
	while i != n:
		for x in range(i, rmin[i]):
			ans[x] = arr[i]
		i = rmin[i]
	ans_.append(ans)
solve()
for i in ans_:
	print(*i)


from collections import deque
n = int(input())
a = list(map(int, input().split()))
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
q = deque()
for i in range(n):
	while bool(len(q)) and a[q[-1]] >= a[i]:
		q.pop()
	if not len(q):
		l[i] = (i + 1) * a[i]
	else:
		l[i] = (i - q[-1]) * a[i] + l[q[-1]]
	q.append(i)
q = deque()
for i in range(n - 1, -1, -1):
	while bool(len(q)) and a[q[-1]] >= a[i]:
		q.pop()
	if not len(q):
		r[i] = (n - i) * a[i]
	else:
		r[i] = (n - i - 1 - (n - q[-1] - 1)) * a[i] + r[q[-1]]
	q.append(i)
mx = 0
for i in range(n):
	if l[mx] + r[mx] - a[mx] <= l[i] + r[i] - a[i]:
		mx = i
res = [0 for _ in range(n)]
res[mx] = a[mx]
for i in range(mx - 1, -1, -1):
	res[i] = min(res[i + 1], a[i])
for i in range(mx + 1, n):
	res[i] = min(res[i - 1], a[i])
print(*res)


n = int(input())
m = list(map(int, input().split()))
(left, right) = ([m[0]], [m[n - 1]])
stack = [(m[0], 1)]
for i in range(1, n):
	res = left[-1]
	num_tmp = 0
	while stack and stack[-1][0] > m[i]:
		res -= stack[-1][0] * stack[-1][1]
		num_tmp += stack[-1][1]
		stack.pop()
	res += m[i] * (num_tmp + 1)
	stack.append((m[i], num_tmp + 1))
	left.append(res)
stack = [(m[n - 1], 1)]
for i in range(n - 2, -1, -1):
	res = right[-1]
	num_tmp = 0
	while stack and stack[-1][0] > m[i]:
		res -= stack[-1][0] * stack[-1][1]
		num_tmp += stack[-1][1]
		stack.pop()
	res += m[i] * (num_tmp + 1)
	stack.append((m[i], num_tmp + 1))
	right.append(res)
(maxi, maxi_ind) = (0, -1)
for i in range(n):
	if left[i] + right[n - i - 1] - m[i] > maxi:
		maxi = left[i] + right[n - i - 1] - m[i]
		maxi_ind = i
i = maxi_ind
ans = [0 for _ in range(n)]
num = m[i]
ans[i] = m[i]
cur = m[i]
for j in range(i - 1, -1, -1):
	cur = min(m[j], cur)
	ans[j] = cur
	num += cur
cur = m[i]
for k in range(i + 1, n):
	cur = min(m[k], cur)
	ans[k] = cur
	num += cur
print(*ans)


import sys
from math import floor, ceil
import bisect
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 30
MOD = 10 ** 7
n = int(ri())
a = Ri()
l = [0] * n
l[0] = a[0]
sta = [0]
for i in range(1, len(a)):
	if a[i] > a[i - 1]:
		l[i] = l[i - 1] + a[i]
		sta.append(i)
	else:
		while len(sta) > 0 and a[sta[-1]] > a[i]:
			sta.pop()
		pos = 0
		if len(sta) == 0:
			l[i] = (i + 1) * a[i]
		else:
			pos = sta[-1]
			l[i] = l[pos] + (i - pos) * a[i]
		sta.append(i)
r = [0] * n
a = a[::-1]
r[0] = a[0]
sta = [0]
for i in range(1, len(a)):
	if a[i] > a[i - 1]:
		r[i] = r[i - 1] + a[i]
		sta.append(i)
	else:
		while len(sta) > 0 and a[sta[-1]] > a[i]:
			sta.pop()
		pos = 0
		if len(sta) == 0:
			r[i] = (i + 1) * a[i]
		else:
			pos = sta[-1]
			r[i] = r[pos] + (i - pos) * a[i]
		sta.append(i)
r = r[::-1]
ind = -1
maxx = -1
a = a[::-1]
for i in range(len(a)):
	if l[i] + r[i] - a[i] > maxx:
		maxx = l[i] + r[i] - a[i]
		ind = i
for i in range(ind + 1, len(a)):
	a[i] = min(a[i - 1], a[i])
for i in range(ind - 1, -1, -1):
	a[i] = min(a[i + 1], a[i])
print(*a)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]

def leftincreasing(l):
	l.append(0)
	d = deque()
	d.append(-1)
	dp = []
	for i in range(len(l) - 1):
		while l[d[-1]] >= l[i]:
			d.pop()
		if i and l[i] >= l[i - 1]:
			dp.append(dp[-1] + l[i])
		elif d[-1] == -1:
			dp.append(l[i] * (i + 1))
		else:
			dp.append(dp[d[-1]] + l[i] * (i - d[-1]))
		d.append(i)
	return dp

def giveans(i, l):
	l1 = []
	l2 = []
	temp = i
	i -= 1
	while i >= 0:
		if not l1:
			l1.append(min(l[i], l[temp]))
		else:
			l1.append(min(l[i], l1[-1]))
		i -= 1
	i = temp + 1
	while i < len(l):
		if not l2:
			l2.append(min(l[i], l[temp]))
		else:
			l2.append(min(l[i], l2[-1]))
		i += 1
	return l1[::-1] + [l[temp]] + l2
n = val()
l = li()
ldec = leftincreasing(l[:])
linc = leftincreasing(l[:][::-1])[::-1]
ans = 0
currans = -float('inf')
for i in range(n):
	if ldec[i] + linc[i] - l[i] > currans:
		currans = ldec[i] + linc[i] - l[i]
		ans = i
	elif currans == ldec[i] + linc[i] - l[i] and l[ans] < l[i]:
		ans = i
print(*giveans(ans, l))


inf = int(2000000000.0) + 1
n = int(input())
a = [-inf] + [int(x) for x in input().split()] + [-inf]

def minLR(n, a):
	ans = [0] * (n + 2)
	st = [0]
	for i in range(1, n + 2):
		while a[st[-1]] > a[i]:
			ans[st.pop()] = i
		st.append(i)
	return ans[1:-1]
a.reverse()
ansL = minLR(n, a)
ansL.reverse()
newL = [n - item for item in ansL]
a.reverse()
ansR = minLR(n, a)
newR = [item - 1 for item in ansR]
L = []
for i in range(n):
	if newL[i] == -1:
		L += [(i + 1) * a[i + 1]]
	else:
		L += [L[newL[i]] + (i - newL[i]) * a[i + 1]]
R = [0] * n
for i in range(n - 1, -1, -1):
	if newR[i] == n:
		R[i] = (n - i) * a[i + 1]
	else:
		R[i] = R[newR[i]] + (newR[i] - i) * a[i + 1]
m = 0
index = -1
for i in range(n):
	t = L[i] + R[i] - a[i + 1]
	if t > m:
		m = t
		index = i
b = a[1:-1]
for i in range(index + 1, n):
	if b[i] > b[i - 1]:
		b[i] = b[i - 1]
for i in range(index - 1, -1, -1):
	if b[i] > b[i + 1]:
		b[i] = b[i + 1]
for i in range(n):
	print(str(b[i]) + ' ', end='')


from sys import stdin, stdout
import traceback
read = stdin.readline
write = stdout.write
writeln = lambda x: write(str(x) + '\n')

def reads(typ=int):
	return list(map(typ, read().split()))

class Sol:

	def __init__(self, n, ms):
		self.n = n
		self.ms = ms

	@classmethod
	def input(cls):
		s = cls(int(read()), reads())
		return s

	def solve(self):
		ret = self.ms
		ls = self.construct_ls(self.ms)
		rs = self.construct_ls(self.ms[::-1])[::-1]
		sums = [ls[i] + rs[i] - self.ms[i] for i in range(self.n)]
		ii = sums.index(max(sums))
		self.go_down(ii, ret)
		self.go_down_right(ii, ret)
		return ret

	def go_down(self, ii, ret):
		lim = self.ms[ii]
		i = ii
		while i >= 0:
			lim = min(lim, self.ms[i])
			ret[i] = lim
			i -= 1

	def go_down_right(self, ii, ret):
		lim = self.ms[ii]
		i = ii
		while i < self.n:
			lim = min(lim, self.ms[i])
			ret[i] = lim
			i += 1

	def construct_ls(self, ms):
		ret = [-1 for _ in range(self.n)]
		floors = []
		cur_sum = 0
		for i in range(self.n):
			mi = ms[i]
			num_mi = 1
			while floors and floors[-1] >= (mi, 1):
				(h, num) = floors.pop()
				num_mi += num
				cur_sum -= (h - mi) * num
			floors.append((mi, num_mi))
			cur_sum += mi
			ret[i] = cur_sum
		return ret
try:
	writeln(' '.join([str(x) for x in Sol.input().solve()]))
except Exception as e:
	print('Got exception:', repr(e))
	print(traceback.format_exc())


n = int(input())
a = [0] + list(map(int, input().split())) + [0]
left = [0] * (n + 2)
right = [0] * (n + 2)
left_min = [0] * (n + 2)
right_min = [0] * (n + 2)
ans = [0] * n
st = [0]
for i in range(1, n + 2):
	while a[st[-1]] > a[i]:
		right_min[st.pop()] = i
	st.append(i)
for j in range(n, -1, -1):
	while a[st[-1]] > a[j]:
		left_min[st.pop()] = j
	st.append(j)
for p in range(1, n + 2):
	if a[p] >= a[p - 1]:
		left[p] = left[p - 1] + a[p]
	else:
		left[p] = left[left_min[p]] + a[p] * (p - left_min[p])
for q in range(n + 1, 0, -1):
	if a[q] <= a[q - 1]:
		right[q - 1] = right[q] + a[q - 1]
	else:
		right[q - 1] = right[right_min[q - 1]] + a[q - 1] * (right_min[q - 1] - q + 1)
imax = 0
mx = 0
for t in range(1, n + 1):
	if left[t] + right[t] - a[t] > mx:
		mx = left[t] + right[t] - a[t]
		imax = t
ans[imax - 1] = a[imax]
for m in range(imax, n):
	ans[m] = min(ans[m - 1], a[m + 1])
for r in range(imax - 2, -1, -1):
	ans[r] = min(ans[r + 1], a[r + 1])
print(' '.join(map(str, ans)))


import sys

def makeMountain(M, i):
	m = M[i]
	curr = m
	left = []
	for j in range(i - 1, -1, -1):
		curr = min(M[j], curr)
		left.append(curr)
	curr = m
	right = []
	for j in range(i + 1, len(M)):
		curr = min(M[j], curr)
		right.append(curr)
	return left[::-1] + [m] + right

def solveEasy(N, M):
	best = tuple()
	for i in range(len(M)):
		total = sum(makeMountain(M, i))
		best = max(best, (total, i))
	i = best[1]
	return ' '.join(map(str, makeMountain(M, i)))

def solve(N, M):

	def makeSlope(M):
		dp = [M[0]]
		stack = [(M[0], 1)]
		start = 0
		for i in range(1, len(M)):
			total = dp[-1]
			while stack and stack[-1][0] >= M[i]:
				(h, w) = stack.pop()
				total -= h * w
				start -= w
			h = M[i]
			w = i - start
			stack.append((h, w))
			start += w
			dp.append(total + h * w)
		return dp
	left = makeSlope(M)
	right = makeSlope(M[::-1])[::-1]
	best = tuple()
	for i in range(len(M)):
		best = max(best, (left[i] + right[i] - M[i], i))
	i = best[1]
	return ' '.join(map(str, makeMountain(M, i)))
input = sys.stdin.readline
(N,) = map(int, input().split())
M = [int(x) for x in input().split()]
ans = solve(N, M)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
m = [int(i) for i in input().split()]
copy = m[:]

def maxsumchecker(arr):
	(stack, lr) = ([], [0] * n)
	for i in range(n):
		while stack and stack[-1][1] > m[i]:
			stack.pop()
		if stack:
			j = stack[-1][0]
			lr[i] = lr[j] + (i - j) * m[i]
		else:
			lr[i] = (i + 1) * m[i]
		stack.append([i, m[i]])
	return lr
l = maxsumchecker(m)
r = maxsumchecker(m.reverse())
r.reverse()
(best, index) = (0, 0)
for i in range(n):
	if l[i] + r[i] - copy[i] > best:
		best = l[i] + r[i] - copy[i]
		index = i
l1 = [0] * n
l1[index] = copy[index]
(i, j) = (index - 1, index + 1)
while i >= 0:
	l1[i] = min(l1[i + 1], copy[i])
	i -= 1
while j < n:
	l1[j] = min(l1[j - 1], copy[j])
	j += 1
print(*l1)


def main():
	import sys
	input = sys.stdin.buffer.readline
	N = int(input())
	A = list(map(int, input().split()))
	inc = [0] * N
	st = [(0, 1)]
	S = 0
	for (i, a) in enumerate(A):
		if a > st[-1][0]:
			S += a
			inc[i] = S
			st.append((a, 1))
		else:
			cnt = 1
			while a < st[-1][0]:
				(b, num) = st.pop()
				S -= b * num
				cnt += num
			S += cnt * a
			inc[i] = S
			st.append((a, cnt))
	dec = [0] * N
	st = [(0, 1)]
	S = 0
	for (i, a) in enumerate(reversed(A)):
		if a > st[-1][0]:
			S += a
			dec[i] = S
			st.append((a, 1))
		else:
			cnt = 1
			while a < st[-1][0]:
				(b, num) = st.pop()
				S -= b * num
				cnt += num
			S += cnt * a
			dec[i] = S
			st.append((a, cnt))
	dec.reverse()
	best = -1
	mid = -1
	for i in range(N - 1):
		if inc[i] + dec[i + 1] > best:
			mid = i
			best = inc[i] + dec[i + 1]
	ans = [0] * N
	ans[mid] = A[mid]
	prev = A[mid]
	for j in range(mid - 1, -1, -1):
		ans[j] = min(prev, A[j])
		prev = ans[j]
	mid += 1
	prev = A[mid]
	for j in range(mid, N):
		ans[j] = min(prev, A[j])
		prev = ans[j]
	print(*ans)
main()


def r(x, d):
	stack = [-1]
	s = [0] * x
	for i in range(x - 1, -1, -1):
		while d[i] < d[stack[-1]] and stack[-1] != -1:
			stack.pop()
		s[i] = (x - i) * d[i] if stack[-1] == -1 else s[stack[-1]] + d[i] * (stack[-1] - i)
		stack += [i]
	return s

def total():
	inf = float('inf')
	n = int(input())
	a = [*map(int, input().split())]
	le = r(n, a)
	a = a[::-1]
	ri = r(n, a)[::-1]
	a = a[::-1]
	ma = 0
	x = 0
	for i in range(n):
		if le[i] + ri[i] - a[i] > ma:
			ma = le[i] + ri[i] - a[i]
			x = i
	for i in range(x + 1, n):
		a[i] = min(a[i], a[i - 1])
	for i in range(x - 1, -1, -1):
		a[i] = min(a[i], a[i + 1])
	print(*a)
total()


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
n = int(input())
m = list(map(int, input().split()))
heap = [[0, -1, 0]]
left = [0] * n
for i in range(n):
	while heap[-1][0] > m[i]:
		heap.pop()
	(_, j, s) = heap[-1]
	heap.append([m[i], i, s + m[i] * (i - j)])
	left[i] = heap[-1][-1]
heap = [[0, -1, 0]]
mm = m[::-1]
right = [0] * n
for i in range(n):
	while heap[-1][0] > mm[i]:
		heap.pop()
	(_, j, s) = heap[-1]
	heap.append([mm[i], i, s + mm[i] * (i - j)])
	right[i] = heap[-1][-1]
right = right[::-1]
score = 0
ind = 0
for i in range(n):
	tmp = left[i] + right[i] - m[i]
	if score < tmp:
		score = tmp
		ind = i
i = ind
ans = [0] * n
ans[i] = m[i]
left = i - 1
while left >= 0:
	ans[left] = min(m[left], ans[left + 1])
	left -= 1
right = i + 1
while right < n:
	ans[right] = min(m[right], ans[right - 1])
	right += 1
print(*ans)


import sys
input = sys.stdin.readline
n = int(input())
m = list(map(int, input().split()))
l = [-1] * n
r = [n] * n
stack = []
for i in range(n):
	while stack and m[stack[-1]] >= m[i]:
		stack.pop()
	if stack:
		l[i] = stack[-1]
	stack.append(i)
stack = []
for i in range(n)[::-1]:
	while stack and m[stack[-1]] >= m[i]:
		stack.pop()
	if stack:
		r[i] = stack[-1]
	stack.append(i)
pre = [0] * n
suf = [0] * n
for i in range(n):
	if l[i] == -1:
		pre[i] = (i + 1) * m[i]
	else:
		pre[i] = pre[l[i]] + (i - l[i]) * m[i]
for i in range(n)[::-1]:
	if r[i] == n:
		suf[i] = (n - i) * m[i]
	else:
		suf[i] = suf[r[i]] + (r[i] - i) * m[i]
ans = 0
idx = -1
for i in range(n):
	if ans < pre[i] + suf[i] - m[i]:
		ans = pre[i] + suf[i] - m[i]
		idx = i
arr = [-1] * n
arr[idx] = m[idx]
for i in range(idx)[::-1]:
	arr[i] = min(arr[i + 1], m[i])
for i in range(idx + 1, n):
	arr[i] = min(arr[i - 1], m[i])
print(*arr)


from collections import deque
n = int(input())
m = list(map(int, input().split()))

def vua(n, a):
	de = deque()
	sp = [0 for _ in range(n)]
	for x in range(n):
		while de and a[de[-1]] > a[x]:
			de.pop()
		if len(de) == 0:
			sp[x] = a[x] * (x + 1)
		else:
			sp[x] = sp[de[-1]] + a[x] * (x - de[-1])
		de.append(x)
	return sp
x = vua(n, m)
y = vua(n, m[::-1])
y = y[::-1]
ans = []
for el in range(n):
	ans.append(x[el] + y[el] - m[el])
maxx = max([_ for _ in range(0, n)], key=lambda i: x[i] + y[i] - m[i])
ind = maxx
for z in range(maxx - 1, -1, -1):
	if m[z] >= m[ind]:
		m[z] = m[ind]
	else:
		ind = z
ind = maxx
for z in range(maxx, n):
	if m[z] >= m[ind]:
		m[z] = m[ind]
	else:
		ind = z
print(*m)


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
q = deque([])
ans = [0] * n
tmp_ans = 0
for i in range(n):
	ind = i
	l_ind = i
	while True:
		if not q:
			q.append((a[i], l_ind))
			tmp_ans += a[i] * (l_ind + 1)
			break
		if q[-1][0] <= a[i]:
			tmp_ans += a[i] * (l_ind - q[-1][1])
			q.append((a[i], l_ind))
			break
		else:
			(height, l) = q.pop()
			if not q:
				tmp_ans -= height * (l + 1)
			else:
				tmp_ans -= height * (l - q[-1][1])
			ind = l
	ans[i] = tmp_ans
b = a[::-1]
q = deque([])
ans2 = [0] * n
tmp_ans = 0
for i in range(n):
	ind = i
	l_ind = i
	while True:
		if not q:
			q.append((b[i], l_ind))
			tmp_ans += b[i] * (l_ind + 1)
			break
		if q[-1][0] <= b[i]:
			tmp_ans += b[i] * (l_ind - q[-1][1])
			q.append((b[i], l_ind))
			break
		else:
			(height, l) = q.pop()
			if not q:
				tmp_ans -= height * (l + 1)
			else:
				tmp_ans -= height * (l - q[-1][1])
			ind = l
	ans2[i] = tmp_ans
max_ans = 0
ind = -1
for i in range(n):
	tmp = ans[i] + ans2[n - 1 - i] - a[i]
	if max_ans < tmp:
		max_ans = tmp
		ind = i
i = ind
ans = [0] * n
tmp = a[i]
l = i
r = i
max_height = a[i]
ans[i] = a[i]
for j in range(0, l)[::-1]:
	if a[j] >= max_height:
		tmp += max_height
	else:
		tmp += a[j]
		max_height = a[j]
	ans[j] = max_height
max_height = a[i]
for j in range(r + 1, n):
	if a[j] >= max_height:
		tmp += max_height
	else:
		tmp += a[j]
		max_height = a[j]
	ans[j] = max_height
print(*ans)


import heapq
n = int(input())
M = [int(i) for i in input().split()]

def f(X):
	H = []
	Ret = [0] * n
	tot = 0
	for (i, x) in enumerate(X):
		haba = 0
		while H:
			h = -heapq.heappop(H)
			(t, y) = (h // 10 ** 6, h % 10 ** 6)
			if t <= x:
				heapq.heappush(H, -(t * 10 ** 6 + y))
				break
			else:
				tot -= (t - x) * y
				haba += y
		heapq.heappush(H, -(x * 10 ** 6 + haba + 1))
		Ret[i] = tot + x
		tot += x
	return Ret
(A1, A2) = (f(M), f(M[::-1])[::-1])
A = [A1[i] + A2[i] - M[i] for i in range(n)]
Ans = [0] * n
ma = max(A)
for i in range(n):
	if A[i] == ma:
		m = i
Ans[m] = M[m]
for i in reversed(range(m)):
	Ans[i] = min(Ans[i + 1], M[i])
for i in range(m + 1, n):
	Ans[i] = min(Ans[i - 1], M[i])
print(*Ans)


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
inf = float('inf')
n = int(input())
a = [*map(int, input().split())]
for x in (0, 1):
	stack = [-1]
	s = [0] * n
	for i in range(n - 1, -1, -1):
		while a[i] < a[stack[-1]] and stack[-1] != -1:
			stack.pop()
		s[i] = (n - i) * a[i] if stack[-1] == -1 else s[stack[-1]] + a[i] * (stack[-1] - i)
		stack += [i]
	a = a[::-1]
	if x:
		ri = s[:][::-1]
	else:
		le = s[:]
s = [i + j - k for (i, j, k) in zip(le, ri, a)]
x = s.index(max(s))
for i in range(x + 1, n):
	a[i] = min(a[i], a[i - 1])
for i in range(x - 1, -1, -1):
	a[i] = min(a[i], a[i + 1])
print(*a)


import sys
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
m = list(map(int, input().split()))
smaller_left = [-1] * n
stack = []
for i in reversed(range(n)):
	val = m[i]
	while stack and val < stack[-1][0]:
		(_, j) = stack.pop()
		smaller_left[j] = i
	stack.append((val, i))
smaller_right = [-1] * n
stack = []
for i in range(n):
	val = m[i]
	while stack and val < stack[-1][0]:
		(_, j) = stack.pop()
		smaller_right[j] = i
	stack.append((val, i))
inc = []
for i in range(n):
	val = m[i]
	j = smaller_left[i]
	if j < 0:
		inc.append(val * (i + 1))
	else:
		inc.append(inc[j] + val * (i - j))
dec = [None] * n
for i in reversed(range(n)):
	val = m[i]
	j = smaller_right[i]
	if j < 0:
		dec[i] = val * (n - i)
	else:
		dec[i] = dec[j] + val * (j - i)
(bestVal, bestId) = (-1, -1)
for i in range(n):
	currVal = inc[i] + dec[i] - m[i]
	if currVal > bestVal:
		bestVal = currVal
		bestId = i
ans = [None] * n
i = bestId
while i >= 0:
	j = smaller_left[i]
	for p in range(i, j, -1):
		ans[p] = m[i]
	i = j
i = bestId
while i < n:
	j = smaller_right[i]
	if j < 0:
		j = n
	for p in range(i, j):
		ans[p] = m[i]
	i = j
print(*ans)


n = int(input())
a = list(map(int, input().split()))
left = [0 for i in range(n)]
right = [0 for i in range(n)]
s = [-1]
for i in range(n - 1, -1, -1):
	while s[-1] != -1 and a[s[-1]] > a[i]:
		s.pop()
	if s[-1] == -1:
		right[i] = a[i] * (n - i)
	else:
		right[i] = right[s[-1]] + a[i] * (s[-1] - i)
	s.append(i)
s = [-1]
for i in range(n):
	while s[-1] != -1 and a[s[-1]] > a[i]:
		s.pop()
	if s[-1] == -1:
		left[i] = a[i] * (i + 1)
	else:
		left[i] = left[s[-1]] + a[i] * (i - s[-1])
	s.append(i)
m = 0
ind = -1
for i in range(n):
	Sum = left[i] + right[i] - a[i]
	if Sum > m:
		m = Sum
		ind = i
i = ind - 1
j = ind + 1
m1 = a[ind]
m2 = a[ind]
while i >= 0:
	if a[i] > m1:
		a[i] = m1
	else:
		m1 = a[i]
	i -= 1
while j < n:
	if a[j] > m2:
		a[j] = m2
	else:
		m2 = a[j]
	j += 1
print(*a)


n = int(input())
m = [0] + list(map(int, input().split())) + [0]
stk = [0] * (n + 2)
(le, ri) = ([0] * (n + 2), [0] * (n + 2))
pos = [0] * (n + 2)
ans = [0] * (n + 2)
top = 0
for i in range(1, n + 1):
	while top and stk[top] > m[i]:
		top -= 1
	le[i] = le[pos[top]] + (i - pos[top]) * m[i]
	top += 1
	(stk[top], pos[top]) = (m[i], i)
top = 0
pos[0] = n + 1
for i in range(n, 0, -1):
	while top and stk[top] > m[i]:
		top -= 1
	ri[i] = ri[pos[top]] + (pos[top] - i) * m[i]
	top += 1
	(stk[top], pos[top]) = (m[i], i)
(_max, idx) = (0, 1)
for i in range(1, n + 1):
	if le[i] + ri[i] - m[i] > _max:
		_max = le[i] + ri[i] - m[i]
		idx = i
ans[idx] = m[idx]
for j in range(idx - 1, 0, -1):
	ans[j] = min(m[j], ans[j + 1])
for j in range(idx + 1, n + 1):
	ans[j] = min(m[j], ans[j - 1])
print(*ans[1:-1])


n = int(input())
arr = list(map(int, input().split()))
back = [0] * n
front = [0] * n
back[n - 1] = arr[n - 1]
stack = [n - 1]
for i in range(n - 2, -1, -1):
	while stack and arr[i] < arr[stack[-1]]:
		stack.pop()
	if len(stack) == 0:
		back[i] = arr[i] * (n - i)
	else:
		back[i] = arr[i] * (stack[-1] - i) + back[stack[-1]]
	stack.append(i)
front[0] = arr[0]
stack = [0]
for i in range(1, n):
	while stack and arr[i] < arr[stack[-1]]:
		stack.pop()
	if len(stack) == 0:
		front[i] = arr[i] * (i + 1)
	else:
		front[i] = arr[i] * (i - stack[-1]) + front[stack[-1]]
	stack.append(i)
pivo = -1
temp = 0
for i in range(n):
	x = front[i] + back[i] - arr[i]
	if x > temp:
		temp = x
		pivo = i
res = [0] * n
l = 1
res[pivo] = str(arr[pivo])
(left_max, right_max) = (arr[pivo], arr[pivo])
while pivo - l >= 0 or pivo + l < len(arr):
	if pivo - l >= 0:
		left_max = min(left_max, arr[pivo - l])
		res[pivo - l] = str(left_max)
	if pivo + l < len(arr):
		right_max = min(right_max, arr[pivo + l])
		res[pivo + l] = str(right_max)
	l += 1
print(' '.join(res))


n = int(input())
a = list(map(int, input().split()))

def wa(a, n):
	incsum = []
	decsum = []
	st1 = []
	thissum = 0
	le = [0, 0]
	st1.append(le)
	for i in a:
		if i >= st1[-1][0]:
			st1.append([i, 1])
			thissum += i
		else:
			c = 0
			while i < st1[-1][0]:
				thissum -= st1[-1][0] * st1[-1][1]
				thissum += i * st1[-1][1]
				c += st1[-1][1]
				st1.pop()
			st1.append([i, c + 1])
			thissum += i
		incsum.append(thissum)
	decsum = []
	thissum = 0
	st1 = [[0, 0]]
	for i in reversed(a):
		if i >= st1[-1][0]:
			st1.append([i, 1])
			thissum += i
		else:
			c = 0
			while i < st1[-1][0]:
				thissum -= st1[-1][0] * st1[-1][1]
				thissum += i * st1[-1][1]
				c += st1[-1][1]
				st1.pop()
			st1.append([i, c + 1])
			thissum += i
		decsum.append(thissum)
	decsum = list(reversed(decsum))
	fans = -1
	thisans = 0
	ansat = -1
	for i in range(n):
		if i == 0:
			thisans = decsum[i]
		elif i == n - 1:
			thisans = incsum[i]
		else:
			thisans = incsum[i] + decsum[i] - a[i]
		if thisans > fans:
			fans = max(fans, thisans)
			ansat = i
	aaa = [0] * n
	aaa[ansat] = a[ansat]
	for i in range(ansat - 1, -1, -1):
		aaa[i] = aaa[i + 1]
		if aaa[i] > a[i]:
			aaa[i] = a[i]
	for i in range(ansat + 1, n):
		aaa[i] = aaa[i - 1]
		if aaa[i] > a[i]:
			aaa[i] = a[i]
	return aaa
print(*wa(a, n))


import sys
n = int(sys.stdin.readline())
inf = int(2000000000.0) + 1
m = [-inf] + [int(x) for x in sys.stdin.readline().split()] + [-inf]
r = [0] * (n + 2)
st = [0]
for i in range(1, n + 2):
	while m[st[-1]] > m[i]:
		r[st.pop()] = i
	st.append(i)
l = [0] * (n + 2)
st1 = [0]
for i in range(n + 1, 0, -1):
	while m[st1[-1]] > m[i]:
		l[st1.pop()] = i
	st1.append(i)
a = [0] * (n + 2)
for i in range(1, n + 1):
	a[i] = a[l[i]] + m[i] * (i - l[i])
b = [0] * (n + 2)
for i in range(n, 0, -1):
	b[i] = b[r[i]] + m[i] * (r[i] - i)
p = -inf
for i in range(n + 1):
	t = a[i] + b[i + 1]
	if t > p:
		q = i
		p = t
for i in range(q - 1, 0, -1):
	if m[i + 1] < m[i]:
		m[i] = m[i + 1]
q += 1
for i in range(1, q + 1):
	print(m[i])
for i in range(q + 1, n + 1):
	if m[i - 1] < m[i]:
		m[i] = m[i - 1]
	print(m[i])


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
le = [l[0]]
r = [l[-1]]
an = 0
d = idx = -1
k = [0]
for i in range(1, n):
	if l[i - 1] <= l[i]:
		le.append(le[i - 1] + l[i])
	else:
		while k and l[k[-1]] >= l[i]:
			k.pop()
		if k:
			j = k[-1]
			le.append(l[i] * (i - j) + le[j])
		else:
			le.append((i + 1) * l[i])
	k.append(i)
k = [0]
p = list(l[::-1])
for i in range(1, n):
	if p[i - 1] <= p[i]:
		r.append(r[i - 1] + p[i])
	else:
		while k and p[k[-1]] >= p[i]:
			k.pop()
		if k:
			j = k[-1]
			r.append(p[i] * (i - j) + r[j])
		else:
			r.append((i + 1) * p[i])
	k.append(i)
for i in range(n):
	x = le[i] + r[n - i - 1] - l[i]
	if x >= an:
		idx = i
		an = x
for i in range(idx + 1, n):
	l[i] = min(l[i], l[i - 1])
for i in range(idx - 1, -1, -1):
	l[i] = min(l[i], l[i + 1])
print(*l)


n = eval(input())
h = list(map(int, input().split()))
L = [0 for i in range(len(h))]
R = [0 for i in range(len(h))]
ans = [0 for i in range(len(h))]
stack = []
for i in range(len(h)):
	while len(stack) and h[stack[-1][0]] >= h[i]:
		stack.pop()
	if len(stack) == 0:
		stack.append((i, (i + 1) * h[i]))
	else:
		stack.append((i, stack[-1][1] + (i - stack[-1][0]) * h[i]))
	L[i] = stack[-1][1]
while len(stack):
	stack.pop()
stack.append((n - 1, 0))
for i in range(len(h) - 1, -1, -1):
	while len(stack) and h[stack[-1][0]] >= h[i]:
		stack.pop()
	if len(stack) == 0:
		stack.append((i, (n - i) * h[i]))
	else:
		stack.append((i, stack[-1][1] + (stack[-1][0] - i) * h[i]))
	R[i] = stack[-1][1]
(mx, which) = (0, -1)
for i in range(len(h)):
	if mx < L[i] + R[i] - h[i]:
		(mx, which) = (L[i] + R[i] - h[i], i)
mn = h[which]
ans[which] = h[which]
for j in range(which - 1, -1, -1):
	mn = min(mn, h[j])
	ans[j] = mn
mn = h[which]
for j in range(which + 1, len(h)):
	mn = min(mn, h[j])
	ans[j] = mn
for i in ans:
	print(i, end=' ')


n = int(input())
a = list(map(int, input().split()))
l = [0] * n
r = [n - 1] * n
stack = [0]
for i in range(1, n):
	while len(stack) > 0 and a[stack[-1]] >= a[i]:
		stack.pop()
	if len(stack) > 0:
		l[i] = stack[-1]
	else:
		l[i] = i
	stack.append(i)
stack = [n - 1]
for i in range(n - 2, -1, -1):
	while len(stack) > 0 and a[stack[-1]] >= a[i]:
		stack.pop()
	if len(stack) > 0:
		r[i] = stack[-1]
	else:
		r[i] = i
	stack.append(i)
area_l = [0] * n
area_r = [0] * n
for i in range(n):
	if l[i] == i:
		area_l[i] = a[i] * (i + 1)
	else:
		area_l[i] = area_l[l[i]] + a[i] * (i - l[i])
for i in range(n - 1, -1, -1):
	if r[i] == i:
		area_r[i] = a[i] * (n - i)
	else:
		area_r[i] = area_r[r[i]] + a[i] * (r[i] - i)
max_area = 0
summit = 0
for i in range(n):
	if area_l[i] + area_r[i] - a[i] > max_area:
		summit = i
		max_area = area_l[i] + area_r[i] - a[i]
for i in range(summit - 1, -1, -1):
	if a[i] > a[i + 1]:
		a[i] = a[i + 1]
for i in range(summit, n - 1):
	if a[i] < a[i + 1]:
		a[i + 1] = a[i]
print(*a)


(N,) = map(int, input().split())
X = list(map(int, input().split()))
stack = [[0, 0, 0]]
ls = []
for i in range(N):
	tmp = [1, X[i], X[i]]
	while stack:
		if stack[-1][1] < tmp[1]:
			tmp[2] = tmp[0] * tmp[1] + stack[-1][2]
			stack.append(tmp)
			break
		else:
			(x, y, z) = stack.pop()
			tmp[0] += x
	ls.append(tmp[2])
stack2 = [[0, 0, 0]]
rs = [0] * N
for i in range(N - 1, -1, -1):
	tmp = [1, X[i], X[i]]
	while stack2:
		if stack2[-1][1] < tmp[1]:
			tmp[2] = tmp[0] * tmp[1] + stack2[-1][2]
			stack2.append(tmp)
			break
		else:
			(x, y, z) = stack2.pop()
			tmp[0] += x
	rs[i] = tmp[2]
mx = 0
ii = 0
for i in range(N):
	if ls[i] + rs[i] - X[i] > mx:
		mx = ls[i] + rs[i] - X[i]
		ii = i
I = ii
i = I
rs = [0] * N
rs[i] = X[i]
b = rs[i]
while i > 0:
	i -= 1
	b = min(X[i], b)
	rs[i] = b
i = I
b = X[i]
while i < N - 1:
	i += 1
	b = min(X[i], b)
	rs[i] = b
print(*rs)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def prev_smaller(arr, N):
	stack = col.deque([])
	stack.append((arr[-1], N - 1))
	res = col.defaultdict(int)
	for i in range(N - 2, -1, -1):
		if len(stack) == 0:
			stack.append((arr[i], i))
			continue
		while len(stack) > 0 and stack[-1][0] > arr[i]:
			res[stack[-1][1]] = i
			stack.pop()
		stack.append((arr[i], i))
	while stack:
		res[stack[-1][1]] = -1
		stack.pop()
	return res

def next_smaller(arr, N):
	stack = col.deque([])
	stack.append((arr[0], 0))
	res = col.defaultdict(int)
	for i in range(1, N):
		if len(stack) == 0:
			stack.append((arr[i], i))
			continue
		while len(stack) > 0 and stack[-1][0] > arr[i]:
			res[stack[-1][1]] = i
			stack.pop()
		stack.append((arr[i], i))
	while stack:
		res[stack[-1][1]] = -1
		stack.pop()
	return res

def solve():
	N = getInt()
	M = getInts()
	prev_less = prev_smaller(M, N)
	next_less = next_smaller(M, N)
	left = [0] * N
	right = [0] * N
	for i in range(N):
		if prev_less[i] == -1:
			left[i] = (i + 1) * M[i]
		else:
			prev = prev_less[i]
			left[i] = left[prev] + (i - prev) * M[i]
	for i in range(N - 1, -1, -1):
		rel_pos = N - i - 1
		if next_less[i] == -1:
			right[i] = (rel_pos + 1) * M[i]
		else:
			nxt = N - next_less[i] - 1
			right[i] = right[next_less[i]] + (rel_pos - nxt) * M[i]
	best = 0
	for i in range(N):
		curr = right[i] + left[i] - M[i]
		if best < curr:
			best = curr
			best_ind = i
	ans = [0] * N
	ans[best_ind] = M[best_ind]
	cur_min = M[best_ind]
	for i in range(best_ind - 1, -1, -1):
		cur_min = min(cur_min, M[i])
		ans[i] = cur_min
	cur_min = M[best_ind]
	for i in range(best_ind + 1, N):
		cur_min = min(cur_min, M[i])
		ans[i] = cur_min
	print(*ans)
	return
solve()


import bisect
n = int(input())
a = list(map(int, input().split(' ')))
summ_l = [0] * n
l = [0] * n
left_book_numbers = [0] * n
left_book_indices = [0] * n
summ_l[0] = a[0]
l[0] = a[0]
left_book_numbers[0] = a[0]
left_book_indices[0] = 0
p = 1
for i in range(1, n):
	if a[i] <= left_book_numbers[0]:
		left_book_numbers[0] = a[i]
		left_book_indices[0] = i
		p = 1
		summ_l[i] = (i + 1) * a[i]
	elif left_book_numbers[p - 1] < a[i]:
		left_book_numbers[p] = a[i]
		left_book_indices[p] = i
		summ_l[i] = summ_l[i - 1] + a[i]
		p += 1
	else:
		j = bisect.bisect_left(left_book_numbers, a[i], 0, p)
		summ_l[i] = summ_l[left_book_indices[j - 1]] + (i - left_book_indices[j - 1]) * a[i]
		left_book_numbers[j] = a[i]
		left_book_indices[j] = i
		p = j + 1
a.reverse()
summ_r = [0] * n
l = [0] * n
left_book_numbers = [0] * n
left_book_indices = [0] * n
summ_r[0] = a[0]
l[0] = a[0]
left_book_numbers[0] = a[0]
left_book_indices[0] = 0
p = 1
for i in range(1, n):
	if a[i] <= left_book_numbers[0]:
		left_book_numbers[0] = a[i]
		left_book_indices[0] = i
		p = 1
		summ_r[i] = (i + 1) * a[i]
	elif left_book_numbers[p - 1] < a[i]:
		left_book_numbers[p] = a[i]
		left_book_indices[p] = i
		summ_r[i] = summ_r[i - 1] + a[i]
		p += 1
	else:
		j = bisect.bisect_left(left_book_numbers, a[i], 0, p)
		summ_r[i] = summ_r[left_book_indices[j - 1]] + (i - left_book_indices[j - 1]) * a[i]
		left_book_numbers[j] = a[i]
		left_book_indices[j] = i
		p = j + 1
summ_r.reverse()
a.reverse()
totals_list = []
for i in range(n):
	totals_list.append(summ_l[i] - a[i] + summ_r[i])
mi = totals_list.index(max(totals_list))
result = [0] * n
result[mi] = a[mi]
i = mi - 1
while i >= 0:
	result[i] = min(result[i + 1], a[i])
	i -= 1
i = mi + 1
while i <= n - 1:
	result[i] = min(result[i - 1], a[i])
	i += 1
for x in result:
	print(x, end=' ')
print()


import sys
input = sys.stdin.readline
R = lambda : list(map(int, input().split()))
(n,) = R()
m = R()
a = [m[0]]
k = [0]
for i in range(1, n):
	if m[i - 1] <= m[i]:
		a.append(a[i - 1] + m[i])
	else:
		while k and m[k[-1]] > m[i]:
			k.pop()
		if k:
			j = k[-1]
			a.append((i - j) * m[i] + a[j])
		else:
			a.append((i + 1) * m[i])
	k.append(i)
p = m[::-1]
b = [p[0]]
k = [0]
for i in range(1, n):
	if p[i - 1] <= p[i]:
		b.append(b[i - 1] + p[i])
	else:
		j = i - 1
		while k and p[k[-1]] > p[i]:
			k.pop()
		if k:
			j = k[-1]
			b.append((i - j) * p[i] + b[j])
		else:
			b.append((i + 1) * p[i])
	k.append(i)
ans = 0
index = 0
for i in range(n):
	temp = a[i] + b[n - i - 1] - m[i]
	if temp > ans:
		ans = temp
		index = i
for i in range(index + 1, n):
	m[i] = min(m[i - 1], m[i])
for i in range(index - 1, -1, -1):
	m[i] = min(m[i + 1], m[i])
print(*m)


n = int(input())
a = list(map(int, input().split()))
all = [a[i] for i in range(n)]
peaks = []
p = []
l = [0 for i in range(n)]
r = [0 for i in range(n)]
st = []
for i in range(0, n):
	while st != [] and a[i] <= a[st[-1]]:
		st.pop()
	if st == []:
		l[i] = a[i] * (i + 1)
	else:
		l[i] = l[st[-1]] + a[i] * (i - st[-1])
	st.append(i)
while st != []:
	st.pop()
for i in range(0, n):
	j = n - i - 1
	while st != [] and a[j] <= a[st[-1]]:
		st.pop()
	if st == []:
		r[j] = a[j] * (i + 1)
	else:
		r[j] = r[st[-1]] + a[j] * (st[-1] - j)
	st.append(j)
maxf = 0
I = 0
for i in range(n):
	if l[i] + r[i] - a[i] >= maxf:
		maxf = l[i] + r[i] - a[i]
		I = i
for i in range(n):
	if i < I:
		a[I - (i + 1)] = min(a[I - i], a[I - (i + 1)])
	if i > I:
		a[i] = min(a[i], a[i - 1])
print(*a)


from sys import stdin

def solve():
	n = int(stdin.readline())
	m = list(map(int, stdin.readline().split()))
	msl = [-1] * n
	msp = [n] * n
	q = []
	for i in range(n):
		while q and m[q[-1]] > m[i]:
			q.pop()
		if q:
			msl[i] = q[-1]
		q.append(i)
	q = []
	for i in range(n - 1, -1, -1):
		while q and m[q[-1]] > m[i]:
			q.pop()
		if q:
			msp[i] = q[-1]
		q.append(i)
	dp1 = [0] * n
	for i in range(n):
		dp1[i] = m[i] * (i - msl[i])
		if msl[i] != -1:
			dp1[i] += dp1[msl[i]]
	dp2 = [0] * n
	for i in range(n - 1, -1, -1):
		dp2[i] += m[i] * (msp[i] - i)
		if msp[i] != n:
			dp2[i] += dp2[msp[i]]
	ansm = 0
	answc = 0
	for i in range(n):
		cur = dp1[i] + dp2[i] - m[i]
		if cur > answc:
			answc = cur
			ansm = i
	i = ansm
	cur = [0] * n
	cur[i] = m[i]
	for j in range(i + 1, n):
		cur[j] = min(cur[j - 1], m[j])
	for j in range(i - 1, -1, -1):
		cur[j] = min(cur[j + 1], m[j])
	print(*cur)
for i in range(1):
	solve()


import sys
from collections import defaultdict
from bisect import bisect_left, bisect_right
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
m = list(map(int, input().split()))
k = 1
while 1 << k < n:
	k += 1
ST = [[float('inf')] * k for _ in range(n)]
for i in range(n):
	ST[i][0] = m[i]
for j in range(1, k):
	for i in range(n):
		if i + (1 << j) > n:
			continue
		ST[i][j] = min(ST[i][j - 1], ST[i + (1 << j - 1)][j - 1])
log_len = [0] * (n + 1)
for i in range(2, n + 1):
	log_len[i] = log_len[i >> 1] + 1
left = [m[0]]
for p in range(1, n):
	pivot = m[p]
	if m[p - 1] <= pivot:
		prev = left[-1]
		left.append(prev + pivot)
	else:
		L = -1
		R = p - 1
		while L + 1 < R:
			M = L + R >> 1
			j = log_len[p - 1 - M + 1]
			val = min(ST[M][j], ST[p - 1 - (1 << j) + 1][j])
			if val > pivot:
				R = M
			else:
				L = M
		if L < 0:
			left.append(pivot * (p + 1))
		else:
			prev = left[L]
			left.append(prev + pivot * (p - L))
right = [m[-1]]
for p in range(1, n):
	pivot = m[~p]
	if m[~(p - 1)] <= pivot:
		prev = right[-1]
		right.append(prev + pivot)
	else:
		L = -1
		R = p - 1
		while L + 1 < R:
			M = L + R >> 1
			j = log_len[p - 1 - M + 1]
			val = min(ST[~(p - 1)][j], ST[~M - (1 << j) + 1][j])
			if val > pivot:
				R = M
			else:
				L = M
		if L < 0:
			right.append(pivot * (p + 1))
		else:
			prev = right[L]
			right.append(prev + pivot * (p - L))
bestSum = -float('inf')
top = -1
for i in range(n):
	currSum = left[i] + right[~i] - m[i]
	if currSum > bestSum:
		bestSum = currSum
		top = i
inv = defaultdict(list)
for (i, val) in enumerate(m):
	inv[val].append(i)
left = []
L = 0
while L <= top:
	j = log_len[top - L + 1]
	val = min(ST[L][j], ST[top - (1 << j) + 1][j])
	posID = bisect_left(inv[val], top + 1) - 1
	pos = inv[val][posID]
	left.extend([val] * (pos - L + 1))
	L = pos + 1
right = []
R = n - 1
while R >= top:
	j = log_len[R - top + 1]
	val = min(ST[top][j], ST[R - (1 << j) + 1][j])
	posID = bisect_right(inv[val], top - 1)
	pos = inv[val][posID]
	right.extend([val] * (R - pos + 1))
	R = pos - 1
ans = left + right[:-1][::-1]
print(*ans)


n = int(input())
m = [-1] + [int(i) for i in input().split()] + [-1]
l = [0] * (n + 2)
r = [0] * (n + 2)
ans_right = [0] * (n + 2)
st = [0]
for i in range(1, n + 2):
	while m[st[-1]] > m[i]:
		ans_right[st.pop()] = i
	st.append(i)
ans_left = [0] * (n + 2)
st_2 = [0]
for i in range(n + 1, 0, -1):
	while m[st_2[-1]] > m[i]:
		ans_left[st_2.pop()] = i
	st_2.append(i)
for i in range(1, n + 1):
	if ans_left[i] == 0:
		l[i] = i * m[i]
	else:
		j = ans_left[i]
		l[i] = l[j] + (i - j) * m[i]
o = 1
for i in range(n, 0, -1):
	if ans_right[i] == n + 1:
		r[i] = o * m[i]
	else:
		j = ans_right[i]
		r[i] = r[j] + (j - i) * m[i]
	o += 1
maxim = -99999999999
y = 0
for t in range(1, n + 1):
	tmp = l[t] + r[t] - m[t]
	if tmp > maxim:
		maxim = tmp
		y = t
ver = y - 1
for i in range(ver - 1, 0, -1):
	if m[i] > m[i + 1]:
		m[i] = m[i + 1]
for i in range(ver + 2, n + 1):
	if m[i] > m[i - 1]:
		m[i] = m[i - 1]
print(*m[1:-1])


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.setrecursionlimit(5 * 10 ** 5 + 5)

def nxt_smaller(a):
	stack = []
	ns = [-1] * len(a)
	for i in range(n):
		while len(stack) != 0 and stack[-1][0] > a[i]:
			curr = stack.pop()
			ns[curr[1]] = i
		stack.append([a[i], i])
	return ns

def prev_smaller(a):
	stack = []
	a.reverse()
	ns = [-1] * len(a)
	for i in range(n):
		while len(stack) != 0 and stack[-1][0] > a[i]:
			curr = stack.pop()
			ns[curr[1]] = n - i - 1
		stack.append([a[i], i])
	a.reverse()
	ns.reverse()
	return ns

def next(a, i):
	if nx[i] != -1:
		return nx[i]
	elif ns[i] == -1:
		nx[i] = (n - i) * a[i]
		return nx[i]
	else:
		nx[i] = (ns[i] - i) * a[i] + next(a, ns[i])
		return nx[i]

def prev(a, i):
	if pv[i] != -1:
		return pv[i]
	elif ps[i] == -1:
		pv[i] = (i + 1) * a[i]
		return pv[i]
	else:
		pv[i] = (i - ps[i]) * a[i] + prev(a, ps[i])
		return pv[i]
n = int(input())
a = [int(i) for i in input().split()]
ns = nxt_smaller(a)
ps = prev_smaller(a)
nx = [-1] * n
pv = [-1] * n
for i in range(n - 1, -1, -1):
	if nx[i] == -1:
		next(a, i)
for i in range(n):
	if pv[i] == -1:
		prev(a, i)
maxi = 0
ind = -1
for i in range(n):
	curr = nx[i] + pv[i] - a[i]
	if curr > maxi:
		maxi = curr
		ind = i
m = a[ind]
ans = [-1] * n
for i in range(ind, n):
	m = min(m, a[i])
	ans[i] = m
m = a[ind]
for i in range(ind - 1, -1, -1):
	m = min(m, a[i])
	ans[i] = m
print(*ans)


_DEBUG = 0
_W = 7

def debug(obj):
	if _DEBUG:
		print(f"{obj}.{' ' * (_W - len(obj))}", end='')
		obj = eval(obj)
		if type(obj) is list:
			print('\t'.join(list(map(str, obj))))
		else:
			print(obj)

def inp():
	global n, arr
	if _DEBUG:
		n = 3
		arr = [10, 6, 8]
	else:
		n = int(input())
		arr = list(map(int, input().split()))
inf = int(1000000000.0) + 1

def getRLess(arrn, n):
	arr = [-inf] + arrn
	answ = [0] * n
	st = [0]
	for i in range(1, n + 1):
		while arr[st[-1]] > arr[i]:
			answ[st.pop() - 1] = i - 1
		st.append(i)
	for i in st[1:]:
		answ[i - 1] = -1
	return answ

def getLLess(arrn, n):
	arr = arrn + [-inf]
	answ = [0] * n
	st = [n]
	for i in range(n - 1, -1, -1):
		while arr[st[-1]] > arr[i]:
			answ[st.pop()] = i
		st.append(i)
	for i in st[1:]:
		answ[i] = -1
	return answ
inp()
(ll, rl) = (getLLess(arr, n), getRLess(arr, n))
debug('arr')
debug('ll')
debug('rl')
(dpl, dpr) = ([0] * (n + 1), [0] * (n + 1))
(prevl, prevr) = ([-1] * n, [n] * n)
for i in range(1, n + 1):
	cl = ll[i - 1]
	if cl == -1:
		dpl[i] = arr[i - 1] * i
	else:
		dpl[i] = dpl[cl + 1] + arr[i - 1] * (i - cl - 1)
		prevl[i - 1] = cl
debug('dpl')
debug('prevl')
for i in range(1, n + 1):
	indEl = n - i
	indElLR = rl[indEl]
	if indElLR == -1:
		dpr[i] = i * arr[indEl]
	else:
		dpr[i] = dpr[n - indElLR] + arr[indEl] * (indElLR - indEl)
		prevr[indEl] = indElLR
debug('dpr')
debug('prevr')
mx = -1
lll = 0
for i in range(n + 1):
	if dpl[i] + dpr[n - i] >= mx:
		lll = i
		mx = dpl[i] + dpr[n - i]
debug('lll')
crl = lll - 1
resl = []
while crl != -1:
	resl.extend([str(arr[crl])] * (crl - prevl[crl]))
	crl = prevl[crl]
crr = lll
debug('crr')
resr = []
while crr != n:
	resr.extend([str(arr[crr])] * (prevr[crr] - crr))
	crr = prevr[crr]
debug('resl')
debug('resr')
print(' '.join(resl[::-1] + resr))


n = int(input())
m = [int(x) for x in input().split()]
nearestLeftSmaller = [-1 for _ in range(n)]
nearestRightSmaller = [-1 for _ in range(n)]
stack = []
for i in range(n):
	while stack and m[i] < m[stack[-1]]:
		nearestRightSmaller[stack[-1]] = i
		stack.pop()
	stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
	while stack and m[i] < m[stack[-1]]:
		nearestLeftSmaller[stack[-1]] = i
		stack.pop()
	stack.append(i)
prefixSums = [-1 for _ in range(n)]
for i in range(n):
	nls = nearestLeftSmaller[i]
	if nls == -1:
		prefixSums[i] = m[i] * (i + 1)
	else:
		prefixSums[i] = m[i] * (i - nls) + prefixSums[nls]
suffixSums = [-1 for _ in range(n)]
for i in range(n - 1, -1, -1):
	nrs = nearestRightSmaller[i]
	if nrs == -1:
		suffixSums[i] = m[i] * (n - i)
	else:
		suffixSums[i] = m[i] * (nrs - i) + suffixSums[nrs]
optimalTotal = -1
optimalIdx = -1
for i in range(n):
	total = prefixSums[i] + suffixSums[i] - m[i]
	if total > optimalTotal:
		optimalTotal = total
		optimalIdx = i
ans = m.copy()
upperLimit = m[optimalIdx]
for i in range(optimalIdx, -1, -1):
	upperLimit = min(upperLimit, m[i])
	ans[i] = upperLimit
upperLimit = m[optimalIdx]
for i in range(optimalIdx, n):
	upperLimit = min(upperLimit, m[i])
	ans[i] = upperLimit

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))
oneLineArrayPrint(ans)


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	m = list(map(int, input().split()))
	sr = [[-1, m[i]] for i in range(n)]
	for i in range(n - 2, -1, -1):
		y = i + 1
		while y != -1 and m[y] >= m[i]:
			y = sr[y][0]
		if y != -1:
			sr[i] = [y, m[i] * (y - i) + sr[y][1]]
		else:
			sr[i][1] = m[i] * (n - i)
	sl = [[-1, m[i]] for i in range(n)]
	for i in range(1, n):
		y = i - 1
		while y != -1 and m[y] >= m[i]:
			y = sl[y][0]
		if y != -1:
			sl[i] = [y, m[i] * (i - y) + sl[y][1]]
		else:
			sl[i][1] = m[i] * (i + 1)
	pref = [0]
	for i in m:
		pref.append(pref[-1] + i)
	val = [0]
	for i in range(1, n - 1):
		if m[i - 1] >= m[i] < m[i + 1] or m[i - 1] > m[i] <= m[i + 1]:
			val.append(i)
	val.append(n - 1)
	ans = 0
	ind = [-1, -1]
	for i in range(len(val) - 1):
		(l, r) = (val[i], val[i + 1])
		ans1 = pref[r] - pref[l + 1] + sl[l][1] + sr[r][1]
		if ans1 > ans:
			ind = [l, r]
			ans = ans1
	val = m[:]
	mini = m[ind[0]]
	for i in range(ind[0], -1, -1):
		mini = min(mini, m[i])
		val[i] = mini
	mini = m[ind[1]]
	for i in range(ind[1], n):
		mini = min(mini, m[i])
		val[i] = mini
	print(*val)
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()


def rmin(a, n):
	ans = [-1] * (n + 2)
	st = [0]
	res = []
	for i in range(1, n + 1):
		while a[st[-1]] > a[i]:
			ans[st.pop()] = n + 1 - i
		st.append(i)
	for i in range(1, n + 1):
		res.append(ans[i])
	return res
n = int(input())
inf = int(2000000000.0) + 1
m = [int(x) for x in input().split()]
m = [-inf] + m + [-inf]
ar = rmin(m, n)
al = rmin(m[::-1], n)[::-1]
lm = [0 for i in range(n)]
rm = lm.copy()
for i in range(n):
	j = n - 1 - i
	lm[i] = m[i + 1] * (i + 1)
	rm[j] = (i + 1) * m[j + 1]
	if al[i] != -1:
		lm[i] += lm[al[i] - 1] - m[i + 1] * al[i]
	if ar[j] != -1:
		rm[j] += rm[n - ar[j]] - m[j + 1] * ar[j]
th = 0
for i in range(n):
	tmp = lm[i] + rm[i] - m[i + 1]
	if tmp > th:
		th = tmp
		tind = i + 1
i = tind + 1
while i < n:
	if m[i + 1] > m[i]:
		m[i + 1] = m[i]
	i += 1
i = tind
while i > 0:
	if m[i - 1] > m[i]:
		m[i - 1] = m[i]
	i -= 1
print(*m[1:n + 1])


import os
import heapq
import sys
import math
import operator
from collections import defaultdict, deque
from bisect import bisect_right, bisect_left
from io import BytesIO, IOBase
from copy import copy

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def inpt():
	return [int(k) for k in input().split()]

def main():
	n = int(input())
	ar = inpt()
	stack = []
	pref = []
	for i in range(n):
		while stack and ar[stack[len(stack) - 1]] > ar[i]:
			stack.pop()
		if not stack:
			pref.append(i)
		else:
			pref.append(stack[len(stack) - 1])
		stack.append(i)
	suf = [0] * n
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and ar[stack[len(stack) - 1]] > ar[i]:
			stack.pop()
		if not stack:
			suf[i] = i
		else:
			suf[i] = stack[len(stack) - 1]
		stack.append(i)
	left = []
	for i in range(n):
		if pref[i] == i:
			left.append((i + 1) * ar[i])
		else:
			left.append(left[pref[i]] + (i - pref[i]) * ar[i])
	right = [0] * n
	for i in range(n - 1, -1, -1):
		if suf[i] == i:
			right[i] = (n - i) * ar[i]
		else:
			right[i] = right[suf[i]] + abs(i - suf[i]) * ar[i]
	(peak, mx) = (0, 0)
	for i in range(n):
		if mx < left[i] + right[i] - ar[i]:
			mx = left[i] + right[i] - ar[i]
			peak = i
	for i in range(peak - 1, -1, -1):
		ar[i] = min(ar[i], ar[i + 1])
	for i in range(peak + 1, n):
		ar[i] = min(ar[i], ar[i - 1])
	for i in ar:
		print(i, end=' ')
	print()
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()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		depth = (stop - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])
direction = {}

@iterative
def rec(l, r, a, rmq, pos):
	if l > r:
		yield 0
	mn = rmq.query(l, r + 1)
	ind = pos[mn][bl(pos[mn], l)]
	rightval = (yield rec(ind + 1, r, a, rmq, pos))
	leftval = (yield rec(l, ind - 1, a, rmq, pos))
	left = (ind - l + 1) * mn + rightval
	right = (r - ind + 1) * mn + leftval
	if left > right:
		direction[l, ind] = mn
	else:
		direction[ind, r] = mn
	yield max(left, right)

def solve(case):
	n = int(inp())
	a = lis()
	rmq = RangeQuery(a)
	pos = {}
	for i in range(n):
		if a[i] not in pos:
			pos[a[i]] = [i]
		else:
			pos[a[i]].append(i)
	for i in pos:
		pos[i].sort()
	rec(0, n - 1, a, rmq, pos)
	for i in direction:
		for j in range(i[0], i[1] + 1):
			a[j] = direction[i]
	print(' '.join((str(a[i]) for i in range(n))))
testcase(1)


from collections import deque

def f():
	global a, n
	return l
n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(n)]
q = deque()
for i in range(n):
	while len(q) and a[q[-1]] >= a[i]:
		q.pop()
	l[i] = (i + 1) * a[i] if len(q) == 0 else (i - q[-1]) * a[i] + l[q[-1]]
	q.append(i)
a.reverse()
r = [0 for i in range(n)]
q = deque()
for i in range(n):
	while len(q) and a[q[-1]] >= a[i]:
		q.pop()
	r[i] = (i + 1) * a[i] if len(q) == 0 else (i - q[-1]) * a[i] + r[q[-1]]
	q.append(i)
a.reverse()
r.reverse()
mx = max([_ for _ in range(0, n)], key=lambda i: l[i] + r[i] - a[i])
for i in range(mx - 1, -1, -1):
	a[i] = min(a[i], a[i + 1])
for i in range(mx + 1, n, 1):
	a[i] = min(a[i], a[i - 1])
print(*a)


def left_nearest_neighbour(array):
	n = len(array)
	neighbours = [-1] * n
	for i in range(1, n):
		j = i - 1
		while j != -1 and array[j] >= array[i]:
			j = neighbours[j]
		neighbours[i] = j
	return neighbours

def right_nearest_neighbour(array):
	n = len(array)
	neighbours = [-1] * n
	for i in reversed(range(n - 1)):
		j = i + 1
		while j != -1 and array[j] >= array[i]:
			j = neighbours[j]
		neighbours[i] = j
	return neighbours

def FindTop(heights):
	n = len(heights)
	left_optim = [0] * n
	left_optim[0] = heights[0]
	right_optim = [0] * n
	right_optim[-1] = heights[-1]
	left_neighbours = left_nearest_neighbour(heights)
	right_neighbours = right_nearest_neighbour(heights)
	for i in range(1, n):
		l_neigh = left_neighbours[i]
		if l_neigh == -1:
			left_optim[i] = heights[i] * (i + 1)
		else:
			left_optim[i] = heights[i] * (i - l_neigh) + left_optim[l_neigh]
	for i in reversed(range(n - 1)):
		r_neigh = right_neighbours[i]
		if r_neigh == -1:
			right_optim[i] = heights[i] * (n - i)
		else:
			right_optim[i] = heights[i] * (r_neigh - i) + right_optim[r_neigh]
	max_heights = [left_optim[i] + right_optim[i] - heights[i] for i in range(n)]
	top = max_heights.index(max(max_heights))
	return (left_neighbours, right_neighbours, top)

def OptimizeHeight(heights):
	n = len(heights)
	(left_neighbours, right_neighbours, top) = FindTop(heights)
	optim_heights = [0] * n
	optim_heights[top] = heights[top]
	i = top
	while i >= 0:
		j = left_neighbours[i]
		if j == -1:
			optim_heights[:i + 1] = [heights[i] for _ in range(i + 1)]
			i = -1
		else:
			optim_heights[j + 1:i + 1] = [heights[i] for _ in range(j + 1, i + 1)]
			i = j
	i = top
	while i >= 0:
		j = right_neighbours[i]
		if j == -1:
			optim_heights[i:] = [heights[i] for _ in range(i, n)]
			i = -1
		else:
			optim_heights[i:j] = [heights[i] for _ in range(i, j)]
			i = j
	return optim_heights
n = int(input())
heights = [int(x) for x in input().split(' ')]
optim_heights = OptimizeHeight(heights)
optim_heights = [str(h) for h in optim_heights]
print(' '.join(optim_heights))


def obhod(l, m, rev):
	if rev:
		m.reverse()
	locmin = []
	number = []
	l[0] = m[0]
	locmin.append(m[0])
	number.append(0)
	for i in range(1, n):
		if m[i] >= m[i - 1]:
			l[i] = l[i - 1] + m[i]
		else:
			while len(locmin) > 0:
				if locmin[-1] > m[i]:
					locmin.pop()
					number.pop()
				else:
					break
			if len(locmin) == 0:
				l[i] = m[i] * (i + 1)
			else:
				l[i] = (i - number[-1]) * m[i] + l[number[-1]]
		locmin.append(m[i])
		number.append(i)
	if rev:
		m.reverse()
		l.reverse()
n = int(input())
m = list(map(int, input().split()))
l = [0] * n
r = [0] * n
obhod(l, m, False)
obhod(r, m, True)
maxi = 0
maxd = 0
for i in range(n):
	if l[i] + r[i] - m[i] > maxd:
		maxd = l[i] + r[i] - m[i]
		maxi = i
for i in range(maxi - 1, -1, -1):
	m[i] = min(m[i], m[i + 1])
for i in range(maxi + 1, n):
	m[i] = min(m[i], m[i - 1])
for i in range(n):
	print(m[i], end=' ')


N = int(input())
m = list(map(int, input().split()))
L = [0] * N
L[0] = -1
stack = [0]
for i in range(1, N):
	while stack and m[stack[-1]] >= m[i]:
		stack.pop()
	if stack:
		L[i] = stack[-1]
	else:
		L[i] = -1
	stack.append(i)
dp = [0] * N
for i in range(0, N):
	if L[i] == -1:
		dp[i] = m[i] * (i + 1)
	else:
		dp[i] = m[i] * (i - L[i]) + dp[L[i]]
m = m[::-1]
R = [0] * N
R[0] = -1
stack = [0]
for i in range(1, N):
	while stack and m[stack[-1]] >= m[i]:
		stack.pop()
	if stack:
		R[i] = stack[-1]
	else:
		R[i] = -1
	stack.append(i)
dp2 = [0] * N
for i in range(0, N):
	if R[i] == -1:
		dp2[i] = m[i] * (i + 1)
	else:
		dp2[i] = m[i] * (i - R[i]) + dp2[R[i]]
m = m[::-1]
dp2 = dp2[::-1]
ans = max((dp[i] + dp2[i] - m[i] for i in range(N)))
for i in range(N):
	if dp[i] + dp2[i] - m[i] == ans:
		res = [0] * N
		res[i] = m[i]
		for j in range(i - 1, -1, -1):
			res[j] = min(res[j + 1], m[j])
		for j in range(i + 1, N):
			res[j] = min(res[j - 1], m[j])
		print(*res)
		break


import operator
from sys import stdin
n = int(input())
floors = [int(x) for x in stdin.readline().split()]
left = [0] * n
right = [0] * n

def left_index(lst):
	m = len(lst)
	S = []
	index_list = []
	for i in range(m):
		while S != []:
			if lst[S[-1]] > lst[i]:
				S.pop()
			else:
				index_list.append(S[-1])
				break
		if S == []:
			index_list.append(i)
		S.append(i)
	return index_list

def left_right(flrs, lst):
	li = left_index(flrs)
	for i in range(n):
		if i == li[i]:
			lst[i] = flrs[i] * (i + 1)
		else:
			lst[i] = lst[li[i]] + (i - li[i]) * flrs[i]
left_right(floors, left)
left_right(floors[::-1], right)
right = right[::-1]
c_max = 0
ind = 0
for i in range(n):
	if left[i] != -1 and right[i] != -1:
		if left[i] + right[i] - floors[i] > c_max:
			c_max = left[i] + right[i] - floors[i]
			ind = i
to_print = [0] * n
to_print[ind] = floors[ind]
m = floors[ind]
for i in range(ind - 1, -1, -1):
	to_print[i] = min(floors[i], m)
	if floors[i] < m:
		m = floors[i]
m = floors[ind]
for i in range(ind + 1, n):
	to_print[i] = min(floors[i], m)
	if floors[i] < m:
		m = floors[i]
for i in to_print:
	print(int(i), end=' ')


n = int(input())
M = list(map(int, input().split()))
area1 = [M[0]] + [0] * (n - 1)
index = [0]
for i in range(1, n):
	if M[i] >= M[i - 1]:
		area1[i] = area1[i - 1] + M[i]
	else:
		while len(index) > 0 and M[i] < M[index[-1]]:
			index.pop()
		if len(index) == 0:
			area1[i] = (i + 1) * M[i]
		else:
			area1[i] = area1[index[-1]] + M[i] * (i - index[-1])
	index.append(i)
area2 = [0] * (n - 1) + [M[-1]]
index = [n - 1]
for i in range(n - 2, -1, -1):
	if M[i] >= M[i + 1]:
		area2[i] = area2[i + 1] + M[i]
	else:
		while len(index) > 0 and M[i] < M[index[-1]]:
			index.pop()
		if len(index) == 0:
			area2[i] = (n - i) * M[i]
		else:
			area2[i] = area2[index[-1]] + M[i] * (index[-1] - i)
	index.append(i)
I = -1
Max = 0
for i in range(n):
	area = area1[i] + area2[i] - M[i]
	if area > Max:
		Max = area
		I = i
for i in range(I - 1, -1, -1):
	if M[i] > M[i + 1]:
		M[i] = M[i + 1]
for i in range(I + 1, n):
	if M[i] > M[i - 1]:
		M[i] = M[i - 1]
print(' '.join(map(str, M)))


import sys, math
import io, os
data = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = 10 ** 9
mod = int(1000000000.0) + 7

def solve(m):
	l = m[:]
	stack = []
	for i in range(n):
		while stack and m[stack[-1]] > m[i]:
			stack.pop()
		if stack:
			ind = stack[-1]
			l[i] = l[ind] + m[i] * (i - ind)
		else:
			l[i] *= i + 1
		stack.append(i)
	return l
n = int(data())
m = mdata()
l = solve(m)
r = solve(m[::-1])[::-1]
max1 = l[0] + r[0] - m[0]
ind = 0
for i in range(1, n):
	if l[i] + r[i] - m[i] > max1:
		max1 = l[i] + r[i] - m[i]
		ind = i
for i in range(ind - 1, -1, -1):
	m[i] = min(m[i], m[i + 1])
for i in range(ind + 1, n):
	m[i] = min(m[i], m[i - 1])
outl(m)


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(input())

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

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv2(N, M):
	ans = -1
	cand = None
	for i in range(N):
		A = [0] * N
		A[i] = M[i]
		for j in range(i - 1, -1, -1):
			A[j] = min(A[j + 1], M[j])
		for j in range(i + 1, N):
			A[j] = min(A[j - 1], M[j])
		sa = sum(A)
		if sa > ans:
			ans = sa
			cand = A
	return cand

@mt
def slv(N, M):

	@mt
	def f(M):
		l = [0]
		s = [(-1, 0)]
		for m in M:
			if m >= s[-1][0]:
				s.append((m, 1))
				l.append(l[-1] + m)
			else:
				t = l[-1]
				count = 0
				while s and s[-1][0] > m:
					(v, c) = s.pop()
					t -= (v - m) * c
					count += c
				s.append((m, count + 1))
				l.append(t + m)
		return l
	L = f(M)
	L.pop(0)
	R = f(reversed(M))
	R.reverse()
	R.pop()
	mv = 0
	mi = -1
	for i in range(N):
		v = L[i] + R[i] - M[i]
		if v > mv:
			mv = v
			mi = i
	i = mi
	A = [0] * N
	A[i] = M[i]
	for j in range(i - 1, -1, -1):
		A[j] = min(A[j + 1], M[j])
	for j in range(i + 1, N):
		A[j] = min(A[j - 1], M[j])
	return A

def main():
	N = read_int()
	M = read_int_n()
	print(*slv(N, M))
main()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
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 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 SegmentTree1:

	def __init__(self, data, default=10 ** 6, 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)
MOD = 10 ** 9 + 7

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
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

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

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
n = int(input())
a = list(map(int, input().split()))
m = a[0]
l = [0] * n
stack = []
for i in range(n):
	m = min(m, a[i])
	if m == a[i]:
		l[i] = i * a[i]
		stack.append(i)
	else:
		while a[stack[-1]] > a[i]:
			stack.pop()
		l[i] = a[i] * (i - 1 - stack[-1]) + a[stack[-1]] + l[stack[-1]]
		stack.append(i)
r = [0] * n
stack = []
res = 0
m = a[-1]
ind = 0
for i in range(n - 1, -1, -1):
	m = min(m, a[i])
	if m == a[i]:
		r[i] = (n - 1 - i) * a[i]
		stack.append(i)
	else:
		while a[stack[-1]] > a[i]:
			stack.pop()
		r[i] = abs(stack[-1] - i - 1) * a[i] + r[stack[-1]] + a[stack[-1]]
		stack.append(i)
	k = l[i] + r[i] + a[i]
	if k > res:
		res = k
		ind = i
ans = [0] * n
ans[ind] = a[ind]
for i in range(ind + 1, n):
	ans[i] = min(ans[i - 1], a[i])
for i in range(ind - 1, -1, -1):
	ans[i] = min(ans[i + 1], a[i])
print(*ans)