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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class C_Ehab_And_Prefix_MEXs {
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
	    PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	    
	    int n = sc.nextInt();
	    
	    int[] vals = new int[n];
	    HashSet<Integer> appearing_vals = new HashSet<>();
	    int max = -1;
	    for(int i = 0; i < n; i++) {
	    	vals[i] = sc.nextInt();
	    	max = Math.max(vals[i], max);
	    	appearing_vals.add(vals[i]);
	    }
	    
	    LinkedList<Integer> vals_to_fill = new LinkedList<>();
	    for(int i = 0; i < max; i++) {
	    	if(!appearing_vals.contains(i))
	    		vals_to_fill.add(i);
	    }
	    
	    ArrayList<Integer> b = new ArrayList<>();
	    // inclusive
	    int last_checked = 0;
	    boolean possible = true;
	    boolean[] indexes_filled = new boolean[max + 1];
	    for(int i = 0; possible && i < n; i++) {	    	
    		if(i > 0 && vals[i] != vals[i - 1]) {
    			b.add(vals[i - 1]);
    			indexes_filled[vals[i - 1]] = true;
    		}else if(vals_to_fill.size() > 0) {
	    		b.add(vals_to_fill.get(0));
	    		indexes_filled[vals_to_fill.get(0)] = true;
	    		vals_to_fill.remove(0);
    		}else {
	    		b.add(500000);
    		}
	    		
	    	for(int j = last_checked; j < vals[i]; j++) {
	    		if(!indexes_filled[j]) {
	    			possible = false;
	    			break;
	    		}
	    	}
	    	last_checked = vals[i];
	    }
	    
	    if(!possible) {
	    	out.println(-1);
	    }else {
	    	b.stream().forEach(x -> System.out.print(x + " "));
	    	System.out.println();
	    }
	    out.close();
	}
	
	private static class MyScanner {
		BufferedReader br;
	    StringTokenizer st;
	 
	    public MyScanner() {
	       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;
	   }
	}
}