Baltic Olympiad in Informatics: 2004 Day 1, Problem 3

A number sequence is given. Your task is to construct an increasing sequence that approximates the given one in the best way. The best approximating sequence is the sequence with the least total deviation from the given sequence.

More precisely, let $t_1,t_2,\dots ,t_N$ be the given sequence. Your task is to construct an increasing sequence $z_1<z_2<\cdots <z_N$.

The total deviation, defined as $|t_1-z_1|+|t_2-z_2|+\cdots +|t_N-z_N|$, should be minimized.

Constraints

$1\le N\le {10}^6$

$0\le t_i,|z_i|\le 2\times {10}^9$

Input Specification

The first line of input contains an integer $N$.

Each of the next $N$ lines describes the given sequence $t$, where the $i+1^{\text{th}}$ line corresponds to $t_i$.

Output Specification

The first line of output must contain the single integer – the minimal possible total deviation.

Each of the next $N$ lines must describe the best approximating sequence $z$, where the $i+1^{\text{th}}$ line corresponds to $z_i$.

If there are several solutions, your program can output any valid sequence with the least total deviation.

Sample Input

7
9
4
8
20
14
15
18

Sample Output

13
6
7
8
13
14
15
18