题目描述

$Xiaomo$是个勤奋的打工人，$One day$，工头$Syl$要求他在一片废弃的砖堆垒中成一个上升阶梯（要求你只能加转，不能减砖），废弃的砖堆从侧面看可以看成

是一条长度为 $n$ 的 数组$X$，而$X$_$i$就是砖堆在位置 $i$ 处的高度，上升阶梯需要满足$X$_$i$ ≤ $X$_$i+1$ ( $1 ≤ i＜ n$ )

$Xiaomo$准备了充足的砖块，但是搬砖机被嫉妒$Xiaomo$魅力的队友们藏了起来，直接导致$Xiaomo$效率大减。 $Xiaomo$作为小南工最强打工人就算是徒手搬

砖也要完成工头$Syl$的任务。

已知$Xiaomo$徒手搬砖平均速度是一秒钟加一块砖头。即1秒钟可以选择任意一个数 $i$ ( $1 ≤ i ≤ n$ )，使$X$_$i$ + 1;

$Xiaomo$想尽快完成任务下班，请问$Xiaomo$最少需要多少秒钟才可以完成任务？

输入格式

第一行输入一个整数 $n$(( $1 ≤ n ≤ 1e5$ )),表示砖堆的长度;

第二行有 $n$ 个整数，第 $i$ 个数 $X$ _$i$代表砖堆i处的高度. ($1 ≤$ $X$_$i$ $≤ 1e7$ )

输出格式

第一行输出一个整数$ans$,表示$Xiaomo$最少需要多少秒钟完成任务.

第二行输出 $n$

第三行紧接着输出 $n$ 个整数,第 $i$ 个数表示 $Xiaomo$ 完成任务后 砖堆i处的高度.

样例

输入

7
4 2 7 6 9 3 10

输出

9
7
4 4 7 7 9 9 10

数据范围与提示

$1 ≤ n ≤ 1e5$

$1 ≤$ $X$_$i$ $≤ 1e7$