#3327. 「SNOI2020」排列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: EntropyIncreaser

题目描述

有一个 n 阶排列 p ,其前 k p_1, p_2, \dots, 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_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\% 的数据,无特殊限制。