Given an array a of length n, find another array, b, of length n such that:

  * for each i (1 ≤ i ≤ n) MEX(\\{b_1, b_2, …, b_i\})=a_i. 



The MEX of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.

Input

The first line contains an integer n (1 ≤ n ≤ 10^5) — the length of the array a.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ i) — the elements of the array a. It's guaranteed that a_i ≤ a_{i+1} for 1≤ i < n.

Output

If there's no such array, print a single line containing -1.

Otherwise, print a single line containing n integers b_1, b_2, …, b_n (0 ≤ b_i ≤ 10^6)

If there are multiple answers, print any.

Examples

Input


3
1 2 3


Output


0 1 2 

Input


4
0 0 0 2


Output


1 3 4 0 

Input


3
1 1 3


Output


0 2 1 

Note

In the second test case, other answers like [1,1,1,0], for example, are valid.
/* ANTHOR KUMAR DAS
KUET ECE 2K18*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sc(a) scanf("%d",&a)
#define sc1(n) scanf("%lld",&n)
#define tc ll tc; sc1(tc);while(tc--)
#define sc2(b,c) scanf("%lld%lld",&b,&c)
#define f(a,b) for(a=0;a<b;a++)
#define pb(a) push_back(a)
#define br break
#define co continue
#define sc3(s) scanf("%s",&s)
#define ye cout<<"YES"<<endl
#define no cout<<"NO"<<endl
int main()
{
    ll n,i,j,k,p,l,t,z,x,q;
    sc1(n);
    ll a[n],b[n];
    bool c[n+10]= {false};

    f(i,n)
    {
        sc1(a[i]);
        c[a[i]]=true;
    }
    k=0;
    for(i=0;i<=n;i++)
    {
        if(c[i]==false)
        {
            b[k]=i;
            c[i]=1;
            k++;
        }
    }
    for(i=n-1;i>=k;)
    {
        if(i==0)
        {
            if(c[0]==0)
            {
                b[i]=0;
            }
            else
            {
                f(j,n)
                {
                    if(c[j]==false)
                    {
                        b[i]=j;
                        br;
                    }
                }
            }
            i--;
        }
        else
        {
            if(a[i]==a[i-1])
            {
                p=i;
                for(j=p-1; j>=0; j--)
                {
                    if(a[j]!=a[j+1])
                    {
                        t=a[j];
                        br;
                    }
                    else
                    {
                        q=j;
                    }
                }
                if(q==0)
                {
                    if(c[0]==false)
                    {
                        t=0;
                    }
                    else
                    {
                        f(j,n+5)
                        {
                            if(c[j]==false)
                            {
                                t=j;
                                br;
                            }
                        }
                    }
                    for(j=q;j<=p;j++)
                    {
                        b[j]=t;
                    }
                    i=-1;
                }
                else{
                    for(j=q;j<p+1;j++)
                    {
                        b[j]=t;
                    }
                    i=q-1;
                }
            }
            else{
                b[i]=a[i-1];
                i--;
            }
        }
    }

f(i,n)
{
    cout<<b[i]<<" ";
}
cout<<endl;




return 0;
}

