这是问题的一个更简单的版本。在此版本中$$$n \le 1000$$$
贝尔兰德首都郊区正在积极建设中。 “Kernel Panic”公司负责管理新贝尔斯克瓦摩天大楼住宅区的建设。所有的摩天大楼都沿着高速公路建造。据了解,该公司已经购买了高速公路沿线的$$$n$$$地块,并准备建造$$$n$$$摩天大楼,每个地块一栋摩天大楼。
建筑师在规划摩天大楼时必须考虑几个要求。首先,由于每个地块上的土地具有不同的属性,因此每个摩天大楼对其最大楼层数都有限制。其次,根据城市的设计规范,一座摩天大楼的左侧和右侧同时有更高的摩天大楼是不可接受的。
正式地,我们将图从 $$$1$$$ 到 $$$n$$$ 编号。那么,如果第 $$$i$$$ 个地块上的摩天大楼有 $$$a_i$$$ 楼层,则必须认为 $$$a_i$$$ 至多为 $$$m_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$$$) — 绘图的数量。
第二行包含整数 $$$m_1, m_2, \ldots, m_n$$$ ($$$1 \leq m_i \leq 10^9$$$) - 每个地块上摩天大楼的每个可能楼层数的楼层数限制。
输出
打印 $$$n$$$ 整数 $$$a_i$$$ - 每座摩天大楼的平面图中的楼层数,满足所有要求,并且所有摩天大楼的楼层总数是最大可能的。
如果可能有多个答案,请打印其中任何一个。
示例
输入 #1
5 1 2 3 2 1
输出 #1
1 2 3 2 1
输入 #2
3 10 6 8
输出 #2
10 6 6
注意
在第一个示例中,您可以建造所有尽可能高的摩天大楼。
在第二个测试示例中,您无法为所有摩天大楼指定最大高度,因为这违反了设计规范限制。答案 $$$[10, 6, 6]$$$ 是最佳答案。请注意,$$$[6, 6, 8]$$$ 的答案也满足所有限制,但不是最优的。