首先考虑 \(k = 1\)，唯一的方案就是倒序输出 \(1\) 到 \(n\)。
我们可以想到，这道题的方法是向已经确定的序列 \(A\) 中插入其他数。
对于一个数 \(x(x < A_i)\)，是不能把它放在 \(A_i\) 前的，不然会使最长上升子序列的长度变大。
为了保证字典序最小，我们得把能放在 \(A_i\) 后的最小的数放它后边。
最后要特殊处理 \(A_k\)，把剩下没有加入答案序列的部分倒序输出。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200500;
int n,k;
int a[N],t[N];
int main() {
cin >> n >> k;
for(int i = 1;i <= k; i++) {
cin >> a[i];
t[a[i]] ++;
}
if(k == 1) {
for(int i = n;i >= 1; i--)
cout << i << " ";
return 0;
}
int cur = 1;
while(cur <= n && t[cur])
cur ++;
for(int i = 1;i < k; i++) {
cout << a[i] << " ";
if(cur < a[i]) {
t[cur] ++;
cout << cur << " ";
cur ++;
}
while(cur <= n && t[cur])
cur ++;
}
for(int i = n; i >= 1; i--) {
if(!t[i] || i == a[k])
cout << i << " ";
}
return 0;
}