911E.Stack Sorting[栈,模拟]

2017-12-30

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$ $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

3 2 1 5 4

input

1
2

5 3
2 3 1

output

-1

input

1
2

5 1
3

output

3 2 1 5 4

input

1
2

5 2
3 4

output

-1

题解

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

1.考虑相邻的两个数 $x,y$ $x<y$ ,则 $x$ 进栈之后就要出栈, $x$ 出栈的条件是 $1~x-1$ 都出栈了.然后大部分的 $-1$ 就可以判掉了. 然后就把x出栈
2.考虑目前出栈已经出到了 $s$ ( $s$ 还没出栈),如果当前的值 $=s$ ,就出栈, $s$ 出栈之后就把栈里剩下的,从栈顶开始,能出栈就出栈(我是新开了一个栈来维护没有出栈的)
3.再从1开始模拟一遍，如果最后不是 $1～n$ 都出栈了且只出栈了一次就输出答案，否则输出 $-1$

#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;
}