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.*;
import java.lang.Math;
import java.util.Random;


public class Solution{

	static int n;
	static int m;
	static char[][] arr;

	static int[] dr = {0,0,1,-1};
	static int[] dc = {1,-1,0,0};



	public static void main(String[] args) throws Exception{

		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int n = fs.nextInt();
		int[] a = fs.readArray(n);
		int[] b = new int[n];

		Queue<Integer> queue = new LinkedList<Integer>();
		int max = a[n-1];

		for(int i=n-1;i>0;i--){
			if(a[i]==a[i-1]){
				if(queue.isEmpty()){
					b[i] = max+1;
				}
				else{
					b[i] = queue.poll();
				}
			}
			else {
				b[i] = a[i-1];
				for(int k = a[i-1]+1;k<a[i];k++)
					queue.add(k);
			}
		}

		if(a[0]==0)
			b[0] = 1;
		else
			b[0] = 0;

		if(!queue.isEmpty()){
			out.println(-1);
		}
		else{
			for(int x: b)
				out.print(x+" ");
			out.println("");
		}
		out.close();

		
	}



	
	

	

	static class FastScanner{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		public String next(){
			while(!st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				} catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		public int nextInt(){
			return Integer.parseInt(next());
		}

		public int[] readArray(int n){
			int[] a = new int[n];
			for(int i=0;i<n;i++)
				a[i] = nextInt();
			return a;
		}

		public long nextLong(){
			return Long.parseLong(next());
		}
	}
}