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.*;

public class Mamo {
    static long mod=998244353;
    static FastReader in=new FastReader();
    static List<Integer >G[];
    static boolean B=true;
    static StringBuilder Sd=new StringBuilder();
    public static void main(String [] args) {
    	//Dir by MohammedElkady
    	int n=in.nextInt(),a[]=new int [n],b[]=new int[n],x=0,v=0,lo=0;
    	ArrayList<Integer> pos=new ArrayList();
    	for(int i=0;i<n;i++) {b[i]=-1;}
    	for(int i=0;i<n;i++)a[i]=in.nextInt();
    for(int i=0;i<n;i++) {
    	if(a[i]==x) {v++;pos.add(i);}
    	else if(a[i]>x+v+1){ 
    		lo=-1;break;
    	}
    	else {
    		int po=x+1;
    		b[i]=x;x=a[i];
    		while(a[i]-->0&&po<x) {
    			b[pos.get(pos.size()-1)]=po;
    			pos.remove(pos.size()-1);
    			po++;
    		}
    	}
    }
    if(lo==-1) {Sd.append(-1+"\n");}
    else {
    	int oo=n+90;
    	for(int i=0;i<n;i++)
    		if(b[i]==-1) {Sd.append(oo+" ");oo++;}
    		else Sd.append(b[i]+" ");
    }
    	System.out.print(Sd);
    }
    static long gcd(long g,long x){if(x<1)return g;else return gcd(x,g%x);}
    static void soutln(String S) {Sd.append(S+"\n");}
    static void sout(String S) {Sd.append(S);}
}
class node implements Comparable<node>{
int f, e;
node(int tt,int ll){
f=tt;e=ll;
}
    @Override
    public int compareTo(node o) {
    return f-o.f;    
    }
}
class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        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;
        }
}
 
class Sorting{
 
 public static int[] bucketSort(int[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 int high = array[0];
 
 int low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
}