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 Solution{
	long rem = 1000000000L;
	InputReader sc;
	boolean singleTest = true;
	
	public void solve(int test){
		int n = nextInt();
		
		int[] a = nextArrInt(n);
		
		int[] b = new int[n];
		
		LinkedList<Integer> indexL = new LinkedList<Integer>();
		LinkedList<Integer> list = new LinkedList<Integer>();
		int val = 0;
		
		for(int i=0; i<n; i++){
			indexL.addLast(i);
			list.addLast(i);
			if(a[i] != val){
				while((val < a[i]) && (list.size() > 0)){
					int el = list.removeFirst();
					int index = indexL.removeLast();
					b[index] = el;
					val++;
				}
			}
			else{
				b[i] = 1000000;
			}
		}
		
		for(int i=0; i<n; i++){
			print(b[i] + " ");
		}
		println("");
	}
	
	
	
	
	
	
	
	
	
	
	
	public int[] initialize(int[] arr, int len, int val){
		for(int i=0; i<len; i++){
			arr[i] = val;
		}
		return arr;
	}
	public long[] initialize(long[] arr, int len, long val){
		for(int i=0; i<len; i++){
			arr[i] = val;
		}
		return arr;
	}
	public boolean[] initialize(boolean[] arr, int len, boolean val){
		for(int i=0; i<len; i++){
			arr[i] = val;
		}
		return arr;
	}
	public int[] initialize(int[] arr, int val){
		return initialize(arr, arr.length, val);
	}
	public long[] initialize(long[] arr, long val){
		return initialize(arr, arr.length, val);
	}
	public boolean[] initialize(boolean[] arr, boolean val){
		return initialize(arr, arr.length, val);
	}
	
	public int nextInt(){
		return sc.nextInt();
	}
	public long nextLong(){
		return sc.nextLong();
	}
	public String next(){
		return sc.next();
	}
	public String nextLine(){
		return sc.nextLine();
	}
	public int[] nextArrInt(int n){
		int[] arr = new int[n];
		for(int i=0; i<n; i++){
			arr[i] = nextInt();
		}
		return arr;
	}
	public long[] nextArrLong(int n){
		long[] arr = new long[n];
		for(int i=0; i<n; i++){
			arr[i] = nextLong();
		}
		return arr;
	}
	public String[] nextArrWord(int n){
		String[] arr = new String[n];
		for(int i=0; i<n; i++){
			arr[i] = next();
		}
		return arr;
	}
	
	public void println(String str){
		System.out.println(str);
	}
	public void println(int num){
		System.out.println(num);
	}
	public void println(long num){
		System.out.println(num);
	}
	public void print(String str){
		System.out.print(str);
	}
	public void print(int num){
		System.out.print(num);
	}
	public void print(long num){
		System.out.print(num);
	}
	public void printArr(int[] arr){
		int n = arr.length;
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	public void printArr(int[] arr, int n){
		print(n+" ");
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	public void printArr(long[] arr){
		int n = arr.length;
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	public void printArr(long[] arr, int n){
		print(n+" ");
		for(int i=0; i<(n-1); i++){
			print(arr[i] + " ");
		}
		println(arr[n-1]);
	}
	
	public Solution(){
		sc = new InputReader();
		
		int tests = 1;
		if(!singleTest){
			tests = sc.nextInt();
		}
        
        for(int t=1; t<=tests; t++){
			solve(t);
        }
	}
	
	public static void main(String[] args){
		new Solution();
	}
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;
	
	public InputReader(){
		InputStream stream = System.in;
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }
	
    public InputReader(InputStream stream){
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }
 
    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()) {
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch(IOException e){
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    public int nextInt(){
        return Integer.parseInt(next());
    }
	
	public long nextLong(){
		return Long.parseLong(next());
	}
	
	public String nextLine(){
		try{
			return reader.readLine();
		}catch(IOException e){
			throw new RuntimeException(e);
		}
	}
}