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.*;
public class Main
{
	public static void main(String[] args)throws Exception
	{
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    PrintWriter pw=new PrintWriter(System.out);
	    int n=(Integer.parseInt(br.readLine()));
	    String s[]=(br.readLine()).split(" ");
	    int a[]=new int[n+1];
	    int ar[]=new int[100001];
	    int b[]=new int[n+1];
	    //LinkedHashSet<Integer> lhs=new LinkedHashSet<Integer>();
	    for(int i=1;i<=n;i++)
	    {
	        a[i]=Integer.parseInt(s[i-1]);
	       // lhs.add(a[i]);
	        ar[a[i]]=i;
	    }
	    int sm=0;
	    int l=0;
	    LinkedList<Integer> small=new LinkedList<Integer>();
	    for(int i=1;i<=n;i++)
	    {
	            if(a[i]!=sm)
	            {
	                b[i]=sm;
	                if(small.size()>0 && small.peek()==sm)
	                {
	                    small.remove();
	                }
	                if(b[i]>l)
	                l=b[i];
	                if(small.size()>0)
	                {
	                    if(small.peek()<=(l+1))
	                    {
	                        sm=(int)(small.remove());
	                    }
	                    else
	                    {
	                        sm=l+1;
	                    }
	                }
	                else
	                {
	                    sm=l+1;
	                }
	                
	            }
	        
	        else
	        {
    	        while(true)
	            {
	                l+=1;
	                if(i>ar[l])
	                {
	                    b[i]=l;
    	                break;
	                }
	                else
	                {
	                    small.add(l);
	                }
	            }
	        }
	    }
	    for(int i=1;i<=n;i++)
	    {
	        pw.print(b[i]+" ");
	    }
	    
	    pw.println();
	    
	    pw.flush();
	}
}
