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 java.io.*;
import java.math.*;
public class C649{

	public static void main(String args[]){
		FastReader sc = new FastReader();
		StringBuilder sb=new StringBuilder();
		int t,i,n;
		t=1;
		while(t-->0){
            n=sc.nextInt();
            int a[]=new int[n];
            int ex[]=new int[n+1];
            int done[]=new int[n+1];
            for(i=0;i<n;i++){
                a[i]=sc.nextInt();
                ex[a[i]]++;
            }
            if(a[0]>=2){
                sb.append(-1).append('\n');
                continue;
            }
            int mex[]=new int[n];
            mex[0]=a[0]==0?1:0;
            if(n==1){
                sb.append(mex[0]).append('\n');
                continue;
            }
            PriorityQueue<node> q=new PriorityQueue<>(new Comparator<node>(){
                @Override
                public int compare(node a,node b){
                    if(a.c==b.c)
                        return a.num-b.num;
                    return a.c-b.c;
                }
            });
            for(i=0;i<=n;i++)
                q.add(new node(i,ex[i]));
            int flag=1;
            for(i=0;i<n;i++){
                node v=q.poll();
                if(v.c>0){
                    flag=0;
                    break;
                }
                if(done[v.num]!=1){
                    mex[i]=v.num;
                    done[v.num]=1;
                }
                ex[a[i]]--;
                q.add(new node(a[i],ex[a[i]]));
            }
            for(i=0;i<n;i++)
                sb.append(mex[i]).append(' ');
            sb.append('\n');

		}
		sb.deleteCharAt(sb.length()-1);
		out.println(sb);
    }
    static class node{
        int c,num;
        public node(int a,int b){
            num=a;
            c=b;
        }
    }

	static PrintWriter out;
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		public FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
			out=new PrintWriter(System.out,true);
		}
		String next(){
			while(st==null || !st.hasMoreElements()){
				try{
					st= new StringTokenizer(br.readLine());
				}
				catch (IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt(){
			return Integer.parseInt(next());
		}
		long nextLong(){
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine(){
			String str = "";
			try{
				str=br.readLine();
			}
			catch(IOException e){
				e.printStackTrace();
			}
			return str;
		}
	}

	public static boolean isPrime(int n) {
		if(n<2) return false;
		for(int i=2;i<=(int)Math.sqrt(n);i++) {
			if(n%i==0) return false;
		}
		return true;
	}

	public static void print(int a[],int l,int r){
		int i;
		for(i=l;i<=r;i++)
			out.print(a[i]+" ");
		out.println();
	}

	public static long fastexpo(long x, long y, long p){
		long res=1;
		while(y > 0){
			if((y & 1)==1)
				res= ((res%p)*(x%p))%p;
			y= y >> 1;			
			x = ((x%p)*(x%p))%p;
		}
		return res;
	}

	public static boolean[] sieve (int n) {
		boolean primes[]=new boolean[n+1];
		Arrays.fill(primes,true);
		primes[0]=primes[1]=false;
		for(int i=2;i*i<=n;i++){
			if(primes[i]){
				for(int j=i*i;j<=n;j+=i)
					primes[j]=false;
			}
		}
		return primes;
	}

	public static long gcd(long a,long b){
        return (BigInteger.valueOf(a).gcd(BigInteger.valueOf(b))).longValue();
    }

    public static void merge(long a[],int l,int m,int r){
        int n1,n2,i,j,k;
        n1=m-l+1;
        n2=r-m;

        long L[]=new long[n1];
        long R[]=new long[n2];

        for(i=0;i<n1;i++)
            L[i]=a[l+i];
        for(j=0;j<n2;j++)
            R[j]=a[m+1+j];

        i=0;j=0;

        k=l;
        while(i<n1&&j<n2){
            if(L[i]<=R[j]){
                a[k]=L[i];
                i++;
            }
            else{
                a[k]=R[j];
                j++;
            }
            k++;
        }

        while(i<n1){
            a[k]=L[i];
            i++;
            k++;
        }
        while(j<n2){
            a[k]=R[j];
            j++;
            k++;
        }
    }
    public static void sort(long a[],int l,int r){
        int m;
        if(l<r){
            m=(l+r)/2;
            sort(a,l,m);
            sort(a,m+1,r);
            merge(a,l,m,r);
        }
    }
}

