Let's suppose you have an array a, a stack s (initially empty) and an array b (also initially empty).
You may perform the following operations until both a and s are empty:
- Take the first element of a, push it into s and remove it from a (if a is not empty);
- Take the top element from s, append it to the end of array b and remove it from s (if s is not empty).
You can perform these operations in arbitrary order.
If there exists a way to perform the operations such that array b is sorted in non-descending order in the end, then array a is called stack-sortable.
For example, [3, 1, 2] is stack-sortable, because b will be sorted if we perform the following operations:
- Remove 3 from a and push it into s;
- Remove 1 from a and push it into s;
- Remove 1 from s and append it to the end of b;
- Remove 2 from a and push it into s;
- Remove 2 from s and append it to the end of b;
- Remove 3 from s and append it to the end of b.
After all these operations b = [1, 2, 3], so [3, 1, 2] is stack-sortable. [2, 3, 1] is not stack-sortable.
You are given k first elements of some permutation p of size n (recall that a permutation of size n is an array of size n where each integer from 1 to n occurs exactly once). You have to restore the remaining n - k elements of this permutation so it is stack-sortable. If there are multiple answers, choose the answer such that p is lexicographically maximal (an array q is lexicographically greater than an array p iff there exists some integer k such that for every i < k qi = pi, and qk > pk). You may not swap or change any of first k elements of the permutation.
Print the lexicographically maximal permutation p you can obtain.
If there exists no answer then output -1.
Input
The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k < n) — the size of a desired permutation, and the number of elements you are given, respectively.
The second line contains k integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the first kelements of p. These integers are pairwise distinct.
Output
If it is possible to restore a stack-sortable permutation p of size n such that the first k elements of p are equal to elements given in the input, print lexicographically maximal such permutation.
Otherwise print -1.
Examples
5 3
3 2 1
3 2 1 5 4
5 3
2 3 1
-1
5 1
3
3 2 1 5 4
5 2
3 4
-1 题意：给你一个数N和一个数 k , 然后是长度为K的数组，
让你构造出一个N的全排列，使之前K项是给定的数组，并且满足这个全排列是stack-sortable
题目给了stack-sortable的定义。 思路：
可以通过折耳根stack-sortab的性质和stack的性质来完成本题。
首先我们要知道这题的一个关键点，当一个数插入到栈的条件是这个数x小于栈中所以的数。
那么我们首先对这K个数进行操作，对于每一个数p[i]，先判断能不能加到栈中（判断条件是栈为空或者比栈顶小），
不能加入到栈中的就一定是符合条件的，那么是直接输出-1.
加入到栈中之后，进行弹出操作，从1开始用一个变量来维护弹出到的最大数，对于栈顶就是能弹出的就先从栈中弹出。
扫完后对剩余的栈中元素进行操作，剩余的栈中元素只所以没有被弹出是因为肯定有some比它小的数在这K个中没出现。
那么我们就把（栈中元素之间）的数倒序分别输出
然后再把前K个没有的数进行倒序输出即可。
因为要求字典序最大，所以是倒序输出这些。 具体细节见accode
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=;while(b){if(b%)ans=ans*a%MOD;a=a*a%MOD;b/=;}return ans;}
inline void getInt(int* p);
const int maxn=;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n,k;
int p[maxn];
int vis[maxn]; int main()
{
//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
gbtb;
cin>>n>>k;
repd(i,,k)
{
cin>>p[i];
vis[p[i]]++;
}
stack<int> st;
int m=inf;
int isok=;
int now=;
repd(i,,k)
{
if(p[i]+==now)
{
now++;
}else
{ if(st.empty())
{
st.push(p[i]);
}else if(st.top()>p[i])
{
st.push(p[i]);
}else
{
isok=;
break;
}
while(st.size()&&st.top()==now+)
{
st.pop();
now++;
} }
}
if(!isok)
{
cout<<-<<endl;
return ;
}
// while(!st.empty()&&st.size()!=1)
// {
// st.pop();
// }
repd(i,,k)
{
cout<<p[i]<<" ";
} while(!st.empty())
{
for (int i = st.top()-;i>=; --i)
{
if(!vis[i])
{
cout<<i<<" ";
vis[i]=;
}else
{
break;
}
/* code */
}
now=max(now,st.top());
st.pop();
} for(int i=n;i>now;i--)
{
cout<<i<<" ";
}
cout<<endl; return ;
} inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '');
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * - ch + '';
}
}
else {
*p = ch - '';
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * + ch - '';
}
}
}