Minimum cost increasing sequence

You are given an integer sequence $A_1, A_2, \dots, A_N$ of length $N$.

Among the integer sequences $B$ that satisfy $B_1 < B_2 < \dots < B_N$, find one that minimizes $|B_1 - A_1| + |B_2 - A_2| + \dots + |B_N - A_N|$. Every element of $B$ fits in a signed 32-bit integer.

Several sequences $B$ can reach the minimum sum. Print the lexicographically smallest one, so make $B_1$ as small as possible, then fix that value and make $B_2$ as small as possible, and continue in the same way.

The first line contains $N$. ($1 \le N \le 10^6$)

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces. ($0 \le A_i \le 2 \times 10^9$)

Print the lexicographically smallest optimal sequence $B$ on $N$ lines, one element per line.

For $A = \{9, 4, 8, 20, 14, 15, 18\}$ the minimum sum is $13$. More than one $B$ reaches it, and $B = \{6, 7, 8, 13, 14, 15, 18\}$ also has sum $13$. The lexicographically smallest one is $B = \{3, 4, 8, 13, 14, 15, 18\}$.