arrangement

Arrangement

There is a permutation of \(1 ... N\). The first \(k\) numbers, \(p_1,p_2,...,p_k\), in the permutation have been determined.

Define a range \([l, r]\) in permutation \(p\) to be a range continuous segment if and only if: $$max(p_l,p_{l+1},...,p_r) - min(p_l,p_{l+1},...,p_r) = r - l$$ Among all possible permutation \(p\), find the maximum number of range continuous segments in the permutation and output the permutation.
If there are multiple permutations that provide the maximum number of range continuous segments please choose any one of them.

Limits

\(1 \leq n \leq 2*10^5\)
\(0 \leq k \leq n\)

Subtasks # Score Constraits
1 10 \(n \leq 10\)
2 20 \(n \leq 22\)
3 10 \(k \leq 1\)
4 20 \(k = n\)
5 40 -

Input format

The first line contains 2 integers \(n, k\), which represent the length of the permutaiton and the predetermined number of numbers.
The second line contains \(k\) space separated positive integers \(p_1,p_2,...,p_k\) representing the known part of the permutation.

Output format

The first line should contain a single integer representing the maximum number of range continuous segments. The second line should contain the permutation.

Samples

Sample Input 1 Sample Output 1
4 1
2
8
2 1 3 4

The optimal solution is \(2, 1, 3, 4\), which has 8 range continuous segments \(( [1], [2], [3], [4], [1, 2], [3, 4], [1, 3], [1, 4])\). \(2, 3, 4, 1\) is another optimal solution

Submitting .cpp to 'arrangement'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 1
Your best score: 0
Source: LOJ #3327

Subtask Score
1 10
2 20
3 10
4 20
5 40