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.io.*;
import java.util.*;
import java.math.*;
import java.util.regex.*;
        public class Solution{
        public static void main (String[] args) {                        
            PrintWriter pw=new PrintWriter(System.out);
            Scanner sc=new Scanner(System.in);
            int t=1;
           // t=sc.nextInt();
            while(t-->0){
                ArrayList<Integer> al=new ArrayList<>();
                HashSet<Integer> h=new HashSet<>();
               int n=sc.nextInt();
               int[] a=new int[n];
               int[] a1=new int[n];
               int s=0;
              
               for(int i=0;i<n;i++){
               a[i]=sc.nextInt();  
               h.add(a[i]);
               }
               int n1=a[n-1];
               n1++; 
              for(int i=0;i<a[n-1];i++)
                if(!h.contains(i))
                  al.add(i);
                  int n2=al.size(); 
                         if(s<n2){
                        a1[0]=al.get(s);
                        s++;}
                        else{
                            a1[0]=n1;
                            n1++;
                        }
                    
                 
               for(int i=1;i<n;i++){
                  if(a[i-1]==a[i]){
                     // pw.print(s);
                      if(s<n2)
                     a1[i]=al.get(s);
                     else{
                     a1[i]=n1;
                     n1++;
                         
                     }
                       s++;
                      
                  }
                       else
                        a1[i]=a[i-1];
                        
                        
               }
               
              for(int i=0;i<n;i++)
                pw.print(a1[i]+" ");
                 
                 //pw.println(n1);
                     }
                       
                       pw.close();
    	}
    }