题目描述

给定一个整数序列$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 (1≤n≤10^6)$，接下来一行共有$n$个数字，表示序列$a_i (0≤a_i≤2×10^9)$。

输出格式

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

第二行输出序列$b_i$，若有多种方案，只需输出其中一种。

5
2 5 46 12 1

47
2 5 11 12 13

提示

【数据范围】

40%的数据$n≤5000$；

60%的数据$n≤300000$；

100%的数据$n≤1000000 , 0≤a_i≤2×10^9$；

题目来源：$Baltic$ $OI$ $2004$ $Day$ $1, Sequence$

感谢@TimeTraveller提供SPJ。