Небоскрёбы

from collections import deque
 
def rmin(a,n) : # поиск всех индексов ближайшего 
    inf = int(2e9) + 1. # меньшего элемента
    a.append(-inf)
    a.appendleft(-inf)
    ans = [-1] * (n + 2)
    st = [0]
    mend = 0
    res = deque()
    for i in range(1, n + 1):
        while a[st[-1]] > a[i]:
            ans[st.pop()] = i - 1
        st.append(i)
    for i in range(1, n + 1):
         res.append(ans[i])
    a.pop()
    a.popleft()
    return res
 
 
n = int(input())
b1 = deque()
b2 = deque()
ps = deque()
ps.append(0)
a = [int(x) for x in input().split()]
while len(a) > 1:
    for i in range(1,n+1):  
        ps.append(ps[-1]+a[i-1])
    a1 = deque(a)
    a2 = deque(a[::-1])
    ar = rmin(a1,n)
    al = rmin(a2,n)
    mend = 0
# ошибка начал складывать индексы, чтобы определить 
    for i in range(len(ar)) :  # элементы массива
        ar[i] += al.pop()
        ind2 = deque()
        if ar[i] < 0 :
            mend += 1
# здесь убираю при наличии минимумы по концам
    while ar[0] < 0 or ar[-1] < 0  or mend > 0 :
        while ar[0] < 0 :
            ar.popleft()
            ps.popleft()
            minm = a1.popleft()
            b1.append(minm)
            mend -= 1
            if mend == 0 : break
        if mend == 0 : break
        while ar[-1] < 0 :
            ar.pop()
            ps.pop()
            minm = a1.pop()
            b2.appendleft(minm)
            mend -= 1
            if mend == 0 : break
# а вот тут посетила мысль организовать рекурсию, но руки так и не выросли толком)))
        if mend > 0 :
            ind2 = len(ar)
            ki = 0
            ind = ar.index(-2)
# определение индекса минимального элемента внутри массива слева
            for i in range(len(ar)) :
                if ar[i] == -2: ki +=1
                if ki == 2:
                    ind2 = i 
                    break
            minm = a1[ind]
            lg = ps[ind] - ps[0] - ind*minm
            rg = ps[ind2] - ps[ind+1] - minm * (ind2  -  1 - ind)
            if lg < rg :
                while ar[0] >= 0 :
                    ar.popleft()
                    b1.append(minm)
                    a1.popleft()
                    ps.popleft()
            else:
                while ar[-1] >= 0 :
                    ar.pop()
                    b2.appendleft(minm)
                    a1.pop()
                    ps.pop()
                mend -= 1
    a = list(a1)
    n = len(a)
a1 = b1 + a1 + b2
print(*a1)

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(input())
    arr = list(map(int, input().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])
 
    print(" ".join(map(str, arr)) + "\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(2e9) + 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()
###################################
#.  Вот этот цикл можно было завернуть в 'def rmin'
###################################
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]
    #print(tmp,th)
    if tmp > th :
        th = tmp
        tind = i + 1
i = tind + 1
#print(i,m)
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(tind)
#print(*al)
#print(*ar)
#print(*lm)
#print(*rm)
print(*m[1:n+1])