该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3327.zip](file://AdditionalFile3327.zip?type=additional_file)

#3327. 「SNOI2020」排列

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

有一个 $n$ 阶排列 $p$，其前 $k$ 位 $p_1, p_2, \dots, p_k$ 已经确定了。

定义排列 $p$ 中，$[l, r]$ 是一个值域连续段当且仅当：

$p$ 中值域连续段个数即所有 $1\le l\le r\le n$ 中值域连续段的总数。

请你求出：所有可能的排列 $p$ 中，值域连续段个数的最大值，以及任意一种方案。

输入格式

第一行两个整数 $n,k$，分别表示排列的阶数和以及确定的位数。

接下来一行由空格分隔的 $k$ 个正整数 $p_1, p_2, \dots, p_k$，表示排列已知的部分。（$k=0$ 则此行为空）

输出格式

输出第一行一个整数表示值域连续段个数的最大值。

第二行 $n$ 个正整数表示任意一种方案。

样例

输入

4 1
2

输出

8
2 1 3 4

最优解为 $2,1,3,4$，有 $8$ 个值域连续段（$[1], [2], [3], [4], [1,2], [3,4], [1,3], [1,4]$）。$2, 3, 4, 1$ 为另一个最优解。

数据范围与提示

对于所有数据，$1\le n\le 2\times 10^5, 0\le k\le n$。

• 对于 $10\%$ 的数据，$n\le 10$；
• 对于另外 $20\%$ 的数据，$n\le 22$；
• 对于另外 $10\%$ 的数据，$k\le 1$；
• 对于另外 $20\%$ 的数据，$k = n$；
• 对于余下 $40\%$ 的数据，无特殊限制。