911E.Stack Sorting[栈,模拟]

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.

Examples

input

1
2
5 3
3 2 1

output

1
3 2 1 5 4

input

1
2
5 3
2 3 1

output

1
-1

input

1
2
5 1
3

output

1
3 2 1 5 4

input

1
2
5 2
3 4

output

1
-1

题解

题意:一个长度为$n$的序列,已知长度为$k$的前缀,然后球一个序列,使按顺序进栈然后出栈顺序可以是1~n,使字典序最大

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) 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]<a[i])
{
if (s!=a[i-1]&&f[a[i-1]]!=1) {printf("-1\n");return 0;}//-1的情况之1
if (f[a[i-1]]!=1)//出栈
{
f[a[i-1]]=1;s=a[i-1]+1;
}
}
if (!f[a[i-1]])//前一个没有出栈就加到另一个栈,相当于当前栈内剩余的元素
{
top1++;
S[top1]=a[i-1];
}
if (s==a[i]) {f[a[i]]=1;s++;}
}
top=k;
while (f[a[top]]&&top>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;
}