思路分析

我们的目标是最大化 $\sum b_i$。由于 $b_i$ 的定义依赖于前缀 $MEX$，并且 $b_i$ 序列是非递减的（$b_1 \le b_2 \le ... \le b_n$），我们希望让 $b_i$ 的值尽可能早地、尽可能大地增长。

$b_i = MEX(\{a_1, ..., a_i\})$。为了让 $b_i$ 的值变大，我们需要让前缀 $\{a_1, ..., a_i\}$ 尽可能地包含从 $0$ 开始的连续整数。

• 为了最大化 $b_1 = MEX(\{a_1\})$，我们应该选择 $a_1=0$（如果数组 $a$ 中有 $0$ 的话）。这样 $b_1=1$。如果选择其他数， $b_1=0$。
• 为了最大化 $b_2 = MEX(\{a_1, a_2\})$，在 $a_1=0$ 的基础上，我们应该选择 $a_2=1$（如果数组 $a$ 中有 $1$ 的话）。这样 $\{a_1, a_2\} = \{0, 1\}$，使得 $b_2=2$。
• 以此类推，为了让 $b_i$ 达到最大可能值 $i$，我们需要让前缀 $\{a_1, ..., a_i\}$ 恰好是 $\{0, 1, ..., i-1\}$。

题目内容

小美有一个长度为 $n$ 的数组 $a$ 。你可以将 $a$ 任意重排。定义一个长度为 $n$ 的数组 $b$，其中 $b_i= MEX(a_1,a_2,...,a_i$)。你需要最大化数组 $b$ 中的元素之和。

你需要输出最大的元素和，以及一个可能的 $a$ 的重排方案。

【名词解释】

$MEX$：整数数组的 $MEX$ 定义为没有出现在数组中的最小非负整数。例如 $MEX${$1,2,3$}$=0、MEX${$0,2,5$}$=1$ 。

输入描述

第一行输入一个整数 $n(1≦n≦2·10^5)$ ，表示数组 $a$ 的长度

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(0≦a_i≦10^9)$ ，表示数组 $a$ 的元素。

输出描述

第一行输出一个整数，表示 $b$ 的元素和。

第二行输出 $n$ 个整数，表示重排后的 $a$ 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查等案正确性。

样例1

输入

3
1 0 1

输出

5
0 1 1

说明

将 $a$ 重排为 {$0,1,1$} 后，数组 $b$ 为 {$1,2,2$} ，元素和为 $5$ 。

可以证明不存在一个重排使得数组 $b$ 的元素和大于 $5$ 。

样例2

输入

6
0 1 2 3 4 5

输出

21
0 1 2 3 4 5