← 返回题目列表

Codeforces · 1313/C1

C1. 摩天大楼(简单版)

中文机器翻译题面 查看原题

这是问题的一个更简单的版本。在此版本中$$$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]$$$ 的答案也满足所有限制,但不是最优的。