#P3327. 「SNOI2020」排列

「SNOI2020」排列

题目描述

有一个 nn 阶排列 pp,其前 kkp1,p2,,pkp_1, p_2, \dots, p_k 已经确定了。

定义排列 pp 中,[l,r][l, r] 是一个值域连续段当且仅当:

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

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

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

输入格式

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

接下来一行由空格分隔的 kk 个正整数 p1,p2,,pkp_1, p_2, \dots, p_k,表示排列已知的部分。(k=0k=0 则此行为空)

输出格式

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

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

4 1
2
8
2 1 3 4

数据范围与提示

对于所有数据,1n2×105,0kn1\le n\le 2\times 10^5, 0\le k\le n

  • 对于 10%10\% 的数据,n10n\le 10
  • 对于另外 20%20\% 的数据,n22n\le 22
  • 对于另外 10%10\% 的数据,k1k\le 1
  • 对于另外 20%20\% 的数据,k=nk = n
  • 对于余下 40%40\% 的数据,无特殊限制。