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.
import java.util.*;

import javax.lang.model.util.ElementScanner6;

import org.w3c.dom.ls.LSException;

import java.lang.*;
import java.io.*;
import java.math.*;
public final class CF
{
    public static void main(String[]args)throws IOException
	{
		//int K=(int)Math.pow(10,9)+7;
        FastReader ob=new FastReader();
        StringBuffer sb=new StringBuffer();
        //int T=ob.nextInt();
        //while(T-->0)
        {
            int n=ob.nextInt();
            int a[]=new int[n];
            int freq[]=new int[1000001];
            int max=-1;
            for (int i=0;i<a.length;i++)
            {
                 a[i]=ob.nextInt();
                 ++freq[a[i]];
                 max=Math.max(max,a[i]);
            }
            ArrayList<Integer> req=new ArrayList<>();
            for(int i=0;i<freq.length;i++)
            {
                 if(freq[i]==0)
                 req.add(i);
            }
            int k=0,mex=0,f=0;
            HashMap<Integer,Integer> hm=new HashMap<>();
            TreeSet<Integer> ts=new TreeSet<>();
            int b[]=new int[n];
            for(int i=0;i<n;i++)
            {
                    if(i==0)
                    {
                         if(a[0]==0)
                         {
                              b[0]=1;
                              mex=0;
                              hm.put(0,1);
                              ts.add(0);
                         }
                         else if(a[0]==1)
                         {
                              b[0]=0;
                              mex=1;
                              hm.put(1,1);
                              ts.add(1);
                         }
                         else
                         {
                              f=1;
                              break;
                         }
                    }
                    else
                    {
                         if(i+1>=a[i])
                         {
                              if(mex==a[i])
                              {
                                   int x=Collections.binarySearch(req, ts.last()+1);
                                   int val=0;
                                   if(x<0)
                                   {
                                        val=req.get(-x-1);
                                   }
                                   else
                                   val=req.get(x);
                                   ts.add(val);
                                   b[i]=val;
                                   hm.put(val,1);

                              }
                              else
                              {
                                   if(hm.containsKey(a[i]))
                                   {
                                        f=1;
                                        break;
                                   }
                                   b[i]=mex;
                                   ts.add(mex);
                                   hm.put(mex,1);
                                   mex=ts.last()+1;
                              }
                         }
                         else
                         {
                              f=1;
                              break;
                         }
                    }
            }
            if(f==1)
            System.out.println("-1");
            else
            {
               for(int i=0;i<n;i++)
               System.out.print(b[i]+" ");
               System.out.println();
            }
        }
        System.out.println(sb);
	}
}
class Pair
{
	int x,y;
	Pair(int x,int y)
	{
		this.x=x;
		this.y=y;
	}
}
class PairComparator implements Comparator<Pair>
{
	public int compare(Pair a,Pair b)
	{
		return a.x-b.x;
	}
}
class FastReader {
    BufferedReader br;
    StringTokenizer st;
    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e)  {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    public String nextLine()
    {
        String s="";
        try {
        s=br.readLine();
        } catch (IOException e)  {
                e.printStackTrace();
            }
        return s;
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    public long nextLong() {
        return Long.parseLong(next());
    }
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}