P4331 [BalticOI 2004] Sequence (Day1)

题目描述

给定一个序列 $t_1,t_2,\dots,t_n$，求出一个递增序列 $z_1,z_2,\dots,z_n$，使得序列 $t_i$ 和 $z_i$ 的各项之差的绝对值之和 $|t_1-z_1|+|t_2-z_2|+\dots+|t_n-z_n|$ 最小。

输入格式

输入文件的第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含一个整数，表示给定的序列 $t_i$。

输出格式

输出文件的第一行应当包含最小的各项之差的绝对值之和。

接下来 $n$ 行，每行应当包含一个整数，表示所求的序列 $z_i$。

输入输出样例 #1

输入 #1

7
9
4
8
20
14
15
18

输出 #1

13
6
7
8
13
14
15
18

说明/提示

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 10^6$，$0\le t_i\le 2\times 10^9$。

说明

译自 BalticOI 2004 Day1 C Sequence。

感谢 @TimeTraveller 提供的 SPJ！