Description

Given a sequence $t_1, t_2, \dots, t_n$, find an increasing sequence $z_1, z_2, \dots, z_n$ such that the sum of absolute differences $|t_1 - z_1| + |t_2 - z_2| + \dots + |t_n - z_n|$ is minimized.

Input Format

The first line contains an integer $n$. The next $n$ lines each contain an integer, representing the given sequence values $t_i$.

Output Format

The first line should contain the minimum sum of absolute differences. The next $n$ lines should each contain an integer, representing the sequence values $z_i$.

7
9
4
8
20
14
15
18

13
6
7
8
13
14
15
18

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 10^6$, $0 \le t_i \le 2 \times 10^9$.

Notes

Translated from BalticOI 2004 Day1 C Sequence. Thanks to @TimeTraveller for providing the SPJ.

Translated by ChatGPT 5