P4331 [BalticOI 2004] Sequence (Day1)

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.

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

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$.

#### 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](https://boi.cses.fi/files/boi2004_day1.pdf). Thanks to @TimeTraveller for providing the SPJ. Translated by ChatGPT 5