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{
	static PrintWriter out=new PrintWriter(System.out);
	public static void main (String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String[] input=br.readLine().trim().split(" ");
		
	
		int n = Integer.parseInt(input[0]);
		int[] arr = new int[n];
		input = br.readLine().trim().split(" ");
		for(int i = 0; i < n ; i++){
		    arr[i] = Integer.parseInt(input[i]);
		}
		printArray(arr);
		
		out.flush();
		out.close();
	}
	public static void printArray(int[] arr)
	{
	    int n = arr.length;
	    int[] freqArray = new int[2 * n + 1];
	    FenwickTree fenTree = new FenwickTree(2 * n);
	    for(int i = n - 1; i >= 0; i--){
	        freqArray[arr[i]]++;
	        if(freqArray[arr[i]] == 1){
	            fenTree.update(arr[i] + 1, 1);
	        }
	    }
	    for(int i = 0; i < n; i++){
	        int mex = binarySearch(fenTree, 2 * n) - 1;
	        out.print(mex + " ");
	        if(freqArray[mex] == 0){
	            fenTree.update(mex + 1, 1);
	            freqArray[mex] = 1;
	        }
	        freqArray[arr[i]]--;
	        if(freqArray[arr[i]] == 0)
	        {
	            fenTree.update(arr[i] + 1, -1);
	        }
	    }
	}
	public static int binarySearch(FenwickTree fenTree, int end)
	{
	    int start = 1;
	    int ans = end;
	    while(start <= end){
	        int mid = (start + end) / 2;
	        int countActual = fenTree.getSum(mid) - fenTree.getSum(start - 1);
	        int countExpected = mid - start + 1;
	        if(countActual < countExpected)
	        {
	            ans = mid;
	            end = mid -1;
	        }
	        else{
	            start = mid + 1;
	        }
	    }
	    return ans;
	}
}

class FenwickTree{
    int[] BIT;
    int n;
    
    public FenwickTree(int n)
    {
        this.n = n;
        BIT = new int[n + 1];
    }
    
    public void update(int index, int increment)
    {
        while(index <= n){
            BIT[index] += increment;
            index += index & (-index);
        }
    }
    
    public int getSum(int index)
    {
        int sum = 0;
        while(index > 0)
        {
            sum += BIT[index];
            index -= index & (-index);
        }
        return sum;
    }
}