This is an easier version of the problem. In this version $n \le 1000$

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 1000$) — 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: interview

Starter code:

Solutions:
def main():
    import sys
    input = sys.stdin.readline

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

    S = -1
    for mid in range(N):
        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]
        prev = A[mid]
        for j in range(mid+1, N):
            ans[j] = min(prev, A[j])
            prev = ans[j]
        if sum(ans) > S:
            S = sum(ans)
            ans_best = ans
    print(*ans_best)


def __starting_point():
    main()

__starting_point()

def solve():
    n = int(input())
    m = list(map(int, input().split()))
    answ = [0] * n
    answc = 0
    for i in range(n):
        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])
        s = sum(cur)
        if s > answc:
            answc = s
            answ = cur
    print(*answ)



for i in range(1):
    solve()


from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n=I()
m=LI()
tot=0
for i in range(n):
    l,r=[],[]
    
    tmp=m[i]
    p=m[i]
    
    # right
    for j in range(i+1,n):
        if m[j]<p:
            p=m[j]
        tmp+=p
        r+=[p]
    
    p=m[i]
    # left
    for j in range(i-1,-1,-1):
        if m[j]<p:
            p=m[j]
        tmp+=p
        l+=[p]
    
    if tmp>tot:
        tot=tmp
        ans=l[::-1]+[m[i]]+r
        
print(*ans)






from math import *
from collections import *
n = int(input())
a = list(map(int,input().split()))
ans = 0
fres = []
for i in range(n):
	s = a[i]
	prev = a[i]
	res = []
	for j in range(i-1,-1,-1):
		prev = min(a[j],prev)
		s += prev
		res.append(prev)
	prev = a[i]
	res = res[::-1]
	res.append(a[i])
	for j in range(i+1,n):
		prev = min(a[j],prev)
		s += prev
		res.append(prev) 
	if(s > ans):
		ans = s
		fres = res[::]
for i in fres:
	print(i,end = " ")

import sys 
input = sys.stdin.readline

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

ans = 0
ind = -1
for i in range(n):
    tmp = a[i]
    l = i
    r = i
    
    max_height = 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]
        
    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]
    if ans < tmp:
        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)

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

fans = 0
height = [0] * n
ma = []
for m in range(n):
    minh = 0
    thisans = 0
    # increasing
    np = False
    height[m] = a[m]
    for i in range(m-1, -1, -1):
        height[i] = height[i + 1]
        if height[i] > a[i]:
            height[i] = a[i]

    for i in range(m+1, n):
        height[i] = height[i-1]
        if height[i] > a[i]:
            height[i] = a[i]
    thisans = sum(height)
    # fans = max(fans, thisans)
    if thisans > fans:
        ma = height.copy()
        fans = thisans
print(*list(ma))

n=int(input())
L=list(map(int,input().split()))
ans=[0]*n
sA=0
for top in range(n):
    r=[]

    if top!=0:
        left=[]
        now=L[top]
        for i in range(top)[::-1]:
            now=min(now,L[i])
            left.append(now)
        r+=left[::-1]
    r.append(L[top])
    if top!=n-1:
        right=[]
        now=L[top]
        for i in range(top+1,n):
            now=min(now,L[i])
            right.append(now)
        r+=right
    sr=sum(r)
    if sA<sr:
        sA=sr
        ans=r
for i in range(n):
    print(ans[i],end=' ')

def f():
    n = int(input())
    M = [int(s) for s in input().split()]
    def goLeftFrom(s):
        sum = 0
        cur = M[s]
        for i in range(s-1,-1,-1):
            cur = min(cur,M[i])
            sum += cur
        return sum
    def goRightFrom(s):
        sum = 0
        cur = M[s]
        for i in range(s+1,n):
            cur = min(cur,M[i])
            sum += cur
        return sum
    ans = 0
    choose = -1
    for i in range(n):
        l = goLeftFrom(i)
        r = goRightFrom(i)
        if l+r+M[i] > ans:
            choose = i
            ans = l+r+M[i]
    rt = [0]*n
    s = choose
    rt[s] = M[s]
    cur = M[s]
    for i in range(s - 1, -1, -1):
        cur = min(cur, M[i])
        rt[i] = cur
    cur = M[s]
    for i in range(s + 1, n):
        cur = min(cur, M[i])
        rt[i] = cur
    print(' '.join(str(num) for num in rt))




f()

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]
#print(forw)
#print(backw)

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]
#print(center)
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)


N = int(input())

m = list(map(int, input().split()))
ans = 0

def sol(k):
    ret = l = r = m[k]
    for i in range(k+1, N):
        if m[i] < r: r = m[i]
        ret += r
    for i in range(k-1, -1, -1):
        if m[i] < l: l = m[i]
        ret += l
    return ret
ans_idx = -1
for i in range(N):
    X = sol(i)
    if ans < X:
        ans = X
        ans_idx = i

l = r = m[ans_idx]
for i in range(ans_idx+1, N):
    if m[i] < r:
        r = m[i]
    else:
        m[i] = r
for i in range(ans_idx-1, -1, -1):
        if m[i] < l:
            l = m[i]
        else:
            m[i] = l
print(*m)

import sys

n=int(sys.stdin.readline())

m=[int(x) for x in sys.stdin.readline().split()]

ans=0

arr=[0]*n

for i in range(n):
	
	floors=m[i]
		
	tmp=[0]*n
	tmp[i]=m[i]

	prev=m[i]
	for j in range(i-1,-1,-1):
		num=min(prev,m[j])
		floors+=num
		tmp[j]=num
		prev=num

	p2=m[i]
	for k in range(i+1,n):
		n2=min(p2,m[k])
		floors+=n2
		tmp[k]=n2
		p2=n2

	if(floors>ans):
		ans=floors
		for g in range(n):
			arr[g]=tmp[g]

for p in range(n):
	print(arr[p],end=" ")
print()


from sys import stdin,stdout
input=stdin.readline
n=int(input())
a=list(map(int,input().split()))
dict=[]
val=-1
i=0
while i<n:
    v=a[i]
    j=i-1
    arr=[]
    pmin=v
    while j>=0:
        v+=min(a[j],pmin)
        arr.append(min(a[j],pmin))
        pmin=min(pmin,min(a[j],pmin))
        j-=1
        
    arr=arr[::-1]
    arr.append(a[i])
    j=i+1
    pmin=v
    while j<n:
        v+=min(a[j],pmin)
        arr.append(min(a[j],pmin))
        pmin=min(pmin,min(a[j],pmin))
        j+=1
    if v>val:

        val=max(val,v)
        dict=arr
    i+=1
print(*dict)
#print(dict.values())
    





n = int(input())
m = list(map(int,input().split()))
ans = []
totalmax = 0
for top in range(n):
    lst = [0]*n
    lst[top] = m[top]
    for i in range(top-1,-1,-1):
        lst[i] = min(lst[i+1],m[i])
    for i in range(top+1,n):
        lst[i] = min(lst[i-1],m[i])
    total = sum(lst)
    if totalmax < total:
        ans = lst
        totalmax = total

print(*ans,sep=" ")

n = int(input())
arr = list(map(int, input().split()))
ans = 0
res = None
for i in range(n):
	temp = list(arr)
	mini = arr[i]
	for j in range(i-1, -1, -1):
		temp[j] = min(temp[j], mini)
		mini = min(mini, temp[j])
	mini = arr[i]
	for j in range(i+1, n):
		temp[j] = min(temp[j], mini)
		mini = min(mini, temp[j])
	s = sum(temp)
	if s > ans:
		ans = s
		res = list(temp)
print(*res)

from copy import copy
from math import *

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


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


def int_inp():
    return int(input())


def float_inp():
    return float(input())


def comp(a):
    return a[0]


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


def __starting_point():
    n = int_inp()
    arr = arr_int_inp()
    outs = []
    for j in range(len(arr)):
        max_el = (j, arr[j])

        new_arr = [0 for _ in range(len(arr))]
        new_arr[max_el[0]] = max_el[1]
        right = max_el[1]
        for i in range(max_el[0], -1, -1):
            new_arr[i] = min(arr[i], right)
            right = new_arr[i]

        left = max_el[1]
        for i in range(max_el[0], len(arr)):
            new_arr[i] = min(arr[i], left)
            left = new_arr[i]

        outs.append(new_arr)

    max_out = (sum(outs[0]), outs[0])
    for out in outs:
        new_sum = sum(out)
        if new_sum > max_out[0]:
            max_out = (new_sum, out)

    for el in max_out[1]:
        print(el, end=' ')

__starting_point()

n = int(input())
m = list(map(int, input().split()))
ans, idx = 0, -1
for i in range(n):
    a = [0] * n
    a[i] = m[i]
    for j in range(i - 1, -1, -1):
        a[j] = min(m[j], a[j + 1])
    for j in range(i + 1, n):
        a[j] = min(m[j], a[j - 1])
    tot = sum(a)
    if tot > ans:
        ans = tot
        idx = i
a = [0] * n
a[idx] = m[idx]
for j in range(idx - 1, -1, -1):
    a[j] = min(m[j], a[j + 1])
for j in range(idx + 1, n):
    a[j] = min(m[j], a[j - 1])
print(*a)