Minimum cost increasing sequence

Time limit2sMemory limit512 MB

Summary

Transform A into a strictly increasing integer sequence B minimizing the sum of |B_i - A_i|, and output the lexicographically smallest such B.

Level: Hard9 of 10
Topics: Dynamic programming, Greedy, Heap
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Hint

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

Examples3

Example 1
Input
```
7
9 4 8 20 14 15 18
```
Expected output
```
3
4
8
13
14
15
18
```
Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
5
1 2 3 4 5
```
Expected output
```
1
2
3
4
5
```