idea来自

题目背景

Y 同学和他的朋友们住在一片美丽的海滨沙滩上。为了让沙滩更加生机盎然，他们决定种植一排漂亮的椰树。Y 同学负责规划种树的方案，他希望在满足所有美学要求的前提下，让这片椰树林看起来尽可能地繁茂。

题目描述

Y 同学在沙滩上准备了 $n$ 个坑，从左到右依次编号为 $1, 2, \dots, n$。他计划在每个坑里种一棵椰树。由于每个坑的土质不同，第 $i$ 个坑中种植的椰树高度 $h_i$ 不能超过一个最大允许值 $a_i$，且必须为正整数，即 $1 \le h_i \le a_i$。

为了整体的美观，这些椰树的种植需要遵循一个特殊的规则： 对于除了最左边和最右边的椰树之外的任意一棵树（即编号 $i$ 满足 $2 \le i \le n-1$ 的树），必须同时满足以下两个条件：

1. 在其左侧，至少存在一棵高度不低于它的树。
2. 在其右侧，也至少存在一棵高度不低于它的树。

更形式化地说，对于任意 $i \in [2, n-1]$，必须存在编号 $j$ 和 $k$（其中 $j < i, k > i$），使得 $h_j \ge h_i$ 且 $h_k \ge h_i$。

Y 同学希望找到一个满足上述所有条件的种树方案（即确定一组高度 $h_1, h_2, \dots, h_n$），并使得所有椰树的高度总和最大。请你帮助他找到这个最优方案。

输入格式

第一行包含一个正整数 $n$，表示坑的数量。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个坑所允许种植的椰树的最大高度。

输出格式

如果存在满足条件的方案：

• 第一行输出一个整数，表示所有椰树的最大高度总和。
• 第二行输出 $n$ 个正整数 $h_1, h_2, \dots, h_n$，表示该方案下每棵椰树的高度。

如果不存在满足条件的方案：

• 仅输出一行字符串 NO。

若有多种方案可以达到最大的高度总和，输出任意一种即可。

样例

样例输入 #1

4
10 20 5 30

样例输出 #1

55
10 10 5 30

提示

样例 1 解释

最终选择的高度方案为 $h = [10, 10, 5, 30]$。

• $h_1=10 \le a_1=10$
• $h_2=10 \le a_2=20$
• $h_3=5 \le a_3=5$
• $h_4=30 \le a_4=30$

所有树的高度均未超过限制。现在检查规则：

• 对于 $i=2$（高度为 $h_2=10$）：其左侧有 $h_1=10$，满足 $h_1 \ge h_2$；其右侧有 $h_4=30$，满足 $h_4 \ge h_2$。规则满足。
• 对于 $i=3$（高度为 $h_3=5$）：其左侧有 $h_1=10$，满足 $h_1 \ge h_3$；其右侧有 $h_4=30$，满足 $h_4 \ge h_3$。规则满足。

可以证明，在此方案下高度总和 $10+10+5+30=55$ 是最大的。

数据范围与约定

• 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$。
• 对于 $100\%$ 的数据，$1 \le a_i \le 10^9$。