Given a permutation $p$ of order $n$, its first $k$ elements $p_1, p_2, \dots, p_k$ are already fixed.

A range $[l, r]$ in the permutation $p$ is defined as a value-range 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-range contiguous segments in $p$ is the total count of all $1\le l\le r\le n$ that satisfy this condition.

Find the maximum possible number of value-range contiguous segments among all possible permutations $p$, and provide one such permutation.

Input

The first line contains two integers $n$ and $k$, representing the order of the permutation and the number of fixed elements, respectively.

The next line contains $k$ space-separated positive integers $p_1, p_2, \dots, p_k$, representing the known part of the permutation. (If $k=0$, this line is empty.)

Output

The first line contains an integer representing the maximum number of value-range contiguous segments.

The second line contains $n$ positive integers representing one such permutation.

Examples

Input 1

4 1
2

Output 1

8
2 1 3 4

Note 1

The optimal solution is $2, 1, 3, 4$, which has $8$ value-range contiguous segments ($[1], [2], [3], [4], [1,2], [3,4], [1,3], [1,4]$). $2, 3, 4, 1$ is another optimal solution.

Subtasks

For all data, $1\le n\le 2\times 10^5, 0\le k\le n$.

• For $10\%$ of the data, $n\le 10$;
• For another $20\%$ of the data, $n\le 22$;
• For another $10\%$ of the data, $k\le 1$;
• For another $20\%$ of the data, $k = n$;
• For the remaining $40\%$ of the data, there are no special restrictions.