[BalticOI 2004] Sequence 数字序列

题目描述

给定一个整数序列 $a_1, a_2, \cdots , a_n$,求出一个递增序列 $b_1 < b_2 < ··· < b_n$,使得序列 $a_i$ 和 $b_i$ 的各项之差的绝对值之和 $|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|$ 最小。

输入输出格式

输入格式


第一行为数字 $n (1≤n≤10^6)$,接下来一行共有 $n$ 个数字,表示序列 $a_i (0≤a_i≤2^{31}-1)$。

输出格式


第一行输出最小的绝对值之和。 第二行输出序列 $b_i$,若有多种方案,只需输出其中一种。

输入输出样例

输入样例 #1

5
2 5 46 12 1

输出样例 #1

47
2 5 11 12 13

说明

【数据范围】 - $40\%$ 的数据 $n≤5000$; - $60\%$ 的数据 $n≤300000$; - $100\%$ 的数据 $n≤10^6 , 0≤a_i≤2^{31}-1$; 题目来源:BalticOI 2004 Day 1, Sequence。 感谢 @TimeTraveller 提供 SPJ。