题目描述

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

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

$$\max(p_l, p_{l+1}, \dots, p_r) - \min(p_l, p_{l+1}, \dots, p_r) = r-l $$

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

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

输入格式

第一行两个整数 $n,k$，分别表示排列的阶数和以及确定的位数。
接下来一行由空格分隔的 $k$ 个正整数 $p_i$，表示排列一直的部分。（$k=0$ 则此行为空）

输出格式

输出第一行一个整数表示值域连续段个数的最大值。
第二行 $n$ 个正整数表示任意一种方案。

4 1
2

8
2 1 3 4

提示

样例说明

对于样例 $1$，最优解为 $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\%$ 的数据，无特殊限制。