给定一个数字序列。你的任务是构造一个单调递增的序列，使其能够最好地逼近给定的序列。最佳逼近序列是指与给定序列的总偏差最小的序列。

更具体地，设 $t_1, t_2, \dots, t_N$ 是给定的数字序列。你的任务是构造一个单调递增的数字序列 $z_1 < z_2 < \dots < z_N$。

使得以下总和达到最小：

$$|t_1 - z_1| + |t_2 - z_2| + \dots + |t_N - z_N|$$

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 1\,000\,000$)。

接下来的 $N$ 行，每行包含一个整数，表示给定序列的元素。其中第 $K+1$ 行包含 $t_K$。

所有元素均满足 $0 \le t_K \le 2\,000\,000\,000$。

输出格式

输出的第一行包含一个整数，表示最小的可能总偏差。

接下来的 $N$ 行，每行包含一个整数，表示最佳逼近序列中对应的元素。

如果存在多个解，你的程序可以输出任意一个能够达到最小总偏差的序列。

样例

输入样例 1

7
9
4
8
20
14
15
18

输出样例 1

13
6
7
8
13
14
15
18