题目描述

给定一个长度为 $N$ 的数列 $A$。我们按照如下规则为 $A$ 对应一个新数列 $B$：

对于每个位置 $i$，$B_i$ 等于 $A$ 中位于 $i$ 右侧、距离 $i$ 最近且严格大于 $A_i$ 的元素的位置。若不存在这样的位置，则 $B_i=0$。

例如，当

$$N=6,\quad A=(3,5,4,1,2,5)$$

时，对应的数列为

$$B=(2,0,6,5,6,0).$$

其中 $B_1=2$，因为 $A_1=3$ 右侧最近的、严格大于它的元素是 $A_2=5$；$B_2=0$，因为 $A_2=5$ 的右侧不存在严格大于它的元素。

现在给定 $N$ 和数列 $B$，请构造一个正整数数列 $A'$，满足：

1. 按上述规则由 $A'$ 得到的数列 $B'$ 与给定的 $B$ 完全相同；
2. $A'$ 中所有元素之和尽可能小。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数，表示数列 $B$。

输出格式

第一行输出一个整数，表示你构造的数列 $A'$ 的元素和。

第二行输出 $N$ 个正整数，表示你构造的数列 $A'$。

数据范围

• $1 \le N \le 4 \cdot 10^5$
• $0 \le B_i \le 4 \cdot 10^5$
• 输出的元素需满足 $1 \le A'_i \le 10^9$

约 $8\%$ 的测试中，最优答案的元素和不超过 $22$。

评分方式

本题为优化评分题。

若出现以下任意情况，该测试点得 $0$ 分：

• 由你输出的数列得到的 $B'$ 与输入的 $B$ 不一致；
• 第一行输出的和不等于第二行数列元素之和；
• 输出数列不合法，例如元素不在允许范围内。

否则，设：

• $\mathrm{sumA}$ 为官方答案的元素和；
• $\mathrm{sumU}$ 为你输出的元素和。

该测试点得分系数为

$$r=1-\sqrt{1-\frac{\mathrm{sumA}+1}{\mathrm{sumU}+1}}.$$

该系数 $r$ 将乘以该测试点的分值，作为你在该测试点上的得分。

当你的和越接近官方答案时，得分越高；若和等于官方答案，则该测试点可获得满分。

样例

10
2 5 5 5 0 7 0 0 10 0

90
9 10 6 4 11 10 11 11 7 11

样例解释

输入给出的

$$B=(2,5,5,5,0,7,0,0,10,0)$$

可以由如下数列得到：

$$A=(1,2,1,1,3,1,2,2,1,2).$$

题目要求你构造一个新的数列 $A'$，使其对应的 $B'$ 与输入的 $B$ 完全相同，并尽量减小元素和。

样例输出为

$$A'=(9,10,6,4,11,10,11,11,7,11).$$

它对应的数列仍然是

$$B'=(2,5,5,5,0,7,0,0,10,0),$$

因此满足合法性要求。

该输出的元素和为 $90$。若官方答案的元素和为 $16$，则该测试点的得分系数约为

$$r=1-\sqrt{1-\frac{16+1}{90+1}}\approx 0.1.$$