2725

2725. 数字序列

题目

给定一个整数序列 $a_1, a_2, ··· , a_n$。

请你求出一个递增序列 $b_1 < b_2 < ··· < b_n$，使得序列 $a_i$ 和 $b_i$ 的各项之差的绝对值之和 $|a_1 - b_1| + |a_2 - b_2| + ··· + |a_n - b_n|$ 最小。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, ··· , a_n$。

输出格式

第一行输出绝对值之和的最小值。

第二行输出 $b_1,b_2, ··· , b_n$。

输出任意合理方案即可。

数据范围

$1 \le n \le 10^6$,

$0 \le a_i \le 2 \times 10^9$

输入样例：

7
9 4 8 20 14 15 18

输出样例：

13
6 7 8 13 14 15 18

题解