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:

1. Remove 3 from $a$ and push it into $s$;
2. Remove 1 from $a$ and push it into $s$;
3. Remove 1 from $s$ and append it to the end of $b$;
4. Remove 2 from $a$ and push it into $s$;
5. Remove 2 from $s$ and append it to the end of $b$;
6. 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$ $q$$i = p$$i$, and $q$$k > p$$k$). 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 $p$1, $p$2, …, $p$$k (1 ≤ p$$i$ ≤ $n$) — the first $k$ elements 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.

## 题解

1.考虑相邻的两个数 $x,y$ \$x

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 #includeusing namespace std;void qmax(int &x,int y) {if (xy) x=y;}int read(){ char s; int k=0,base=1; while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s))); if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar(); while(isdigit(s)){k=k*10+(s^'0');s=getchar();} return k*base;}void write(int x){ if(x<0){putchar('-');write(-x);} else{if(x/10)write(x/10);putchar(x%10+'0');}}int n,k,s,top,sum,T;int a[201000];int S[201000],top1;int f[201000];int h[201000];int l[201000],ans[201000],p;int main(){ n=read();k=read(); s=1; for (int i=1;i<=k;i++) a[i]=read(); for (int i=1;i<=k;i++) { h[a[i]]=1; while (S[top1]==s&&top1!=0)//之前没出栈 { f[s]=1;top1--;s++; } if (i==1) continue; if (a[i-1]0) top--; //把前面的出栈 for (int i=1;i<=k;i++) p++,ans[p]=a[i]; while (s<=n) //模拟 { while (f[a[top]]&&top>0) top--; if (a[top]==s&&top!=0) { while (sum) { p++;ans[p]=l[sum]; if (h[ans[p]])//已经出栈了 { printf("-1");return 0; } h[ans[p]]=1; sum--; } s++; f[a[top]]=1; } else{sum++;l[sum]=s;s++;} } while (f[a[top]]&&top>0) top--; //剩下的 if (top!=0) { printf("-1"); return 0; } while (sum) { p++;ans[p]=l[sum];sum--; } for (int i=1;i<=p;i++) printf("%d ",ans[i]); return 0;}