P6795 [SNOI2020] Permutation

There is a permutation $p$ of length $n$. The first $k$ positions $p_1, p_2, \cdots, p_k$ have already been fixed. In the permutation $p$, define that $[l, r]$ is a value-contiguous segment if and only if: $$\max(p_l, p_{l+1}, \dots, p_r) - \min(p_l, p_{l+1}, \dots, p_r) = r-l$$ The number of value-contiguous segments in $p$ is the total count of such segments among all $1 \le l \le r \le n$. You need to find, among all possible permutations $p$, the maximum possible number of value-contiguous segments, and output any one permutation that achieves it.

The first line contains two integers $n, k$, representing the length of the permutation and the number of fixed positions. The next line contains $k$ positive integers $p_i$ separated by spaces, representing the fixed part of the permutation. (If $k = 0$, this line is empty.)

Output the first line with one integer, the maximum number of value-contiguous segments. Output the second line with $n$ positive integers, representing any one valid permutation.

#### Sample Explanation For sample $1$, an optimal solution is $2,1,3,4$, which has $8$ value-contiguous segments ($[1], [2], [3], [4], [1,2], [3,4], [1,3], [1,4]$). $2,3,4,1$ is another optimal solution. #### Constraints For all testdata, $1 \le n \le 2\times 10^5, 0 \le k \le n$. - For $10\%$ of the testdata, $n \le 10$; - For another $20\%$ of the testdata, $n \le 22$; - For another $10\%$ of the testdata, $k \le 1$; - For another $20\%$ of the testdata, $k = n$; - For the remaining $40\%$ of the testdata, there are no special restrictions. Translated by ChatGPT 5