Skyscrapers (easy version)

## 题目描述 这题是 [CF1313C2](https://www.luogu.com.cn/problem/CF1313C2) 的简单版本。这个版本中 $1 \leq n \leq 1000$。 Berland要起摩天大厦了。所有的摩天大厦都在高速公路附近建。发展商买了 $n$ 块地准备建 $n$ 栋摩天大厦，一块地一栋。 当规划一间摩天大厦的时候，建筑师要考虑一些条件。 第一，因为每栋摩天大厦有不同的用途，所以每栋摩天大厦都有自己的层数限制，也就是说，这栋摩天大厦的高度不能超过给定的值 $m_i$。 第二，根据城市的建设规则，一栋摩天大厦不能同时在左右有比它高的摩天大厦。 如果规范地表示，让我们把地编上一个编号从 $1$ 到 $n$。那么如果在第 $i$ 块地的摩天大厦有 $a_i$ 层，那么我们需要保证 $1 \le a_i \le m_i$。另外，这里不可以有整数 $j$ 和 $k$ 满足 $j < i < k$ 并且 $a_j > a_i < a_k$。第 $j, k$ 块地并不需要与第 $i$ 块地相邻。 发展商想要使得每块地上摩天大厦的楼层数之和最大。也请帮他找出在**任意一个**最优状况中每个摩天大厦的高度。也就是，要让建筑师考虑的条件都符合，而且要使得每块地上摩天大厦的楼层数之和最大。 ## 输入格式 第一行有一个整数 $n$ $(1 \leq n \leq 1000)$，表示发展商购买了 $n$ 块地。 第二行，$n$ 个整数 $m_1, m_2, \ldots, m_n$ $(1 \leq m_i \leq 10^9)$，表示每块地上建摩天大厦层数的限制。 ## 输出格式 输出 $n$ 个整数 $a_i$，表示在最优状况中每个摩天大厦的高度，而且要符合建筑师考虑的条件。如果答案有多种，你可以输出任何一种。

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.

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.

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.

5
1 2 3 2 1

1 2 3 2 1

3
10 6 8

10 6 6

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.