Description

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.

Input Format

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 Format

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.

4 1
2

8
2 1 3 4

Hint

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