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 three {

	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("three"));

		int n = Integer.parseInt(in.readLine());  
		int[] a = new int[n];
		int[] b = new int[n];
		//HashSet<Integer> bhas = new HashSet<>();
		TreeSet<Integer> bneeds = new TreeSet<>();
		//HashSet<Integer> ahas = new HashSet<>();
		//ArrayList<Integer> ahas = new ArrayList<>();
		//TreeSet<Integer> ahas = new TreeSet<>();
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i=0; i<n; i++) {
			a[i] = Integer.parseInt(st.nextToken()); 
			//ahas.add(a[i]);
		}
		for (int j = 0;j < a[n-1]; j++) bneeds.add(j);
		int prevval = a[n-1]+1;
		int curval = 0;
		boolean got = false;
		//boolean cont = true;
		for (int i=0; i<n; i++) {
			got = false;
			if (bneeds.size() == 0) {
				got = true;
				if (a[i] == 0) curval = 1;
				else curval = 0;
			}
			else {
				for (Integer cur : bneeds) {
					if (a[i] != cur) {
						curval = cur;
						got = true;
						break;
					}
				}
			}
			if (got) {
				b[i] = curval;
				bneeds.remove(curval);
			}
			else {
				b[i] = prevval;
				prevval++;
			}
			//bhas.add(curval);
			//if (i != n-1 && a[i] != a[i+1]) {
				//ahas.remove(0);
				//ahas.remove(a[i]);
			//}
			curval = 0;
		}
		for (int i=0; i<n; i++) System.out.print(b[i] + " ");
	}
}

// always increase if can and check ahas

/*
	if (a[0] == 0) {
	prevel = 1;
	b[0] = 1;
	bhas.add(1);
	}
	else if (a[0] == 1) {
	prevel = 0;
	b[0] = 0;
	bhas.add(0);
	}
	else {
	System.out.println(-1);
	cont = false;
	}
	
	if (cont) {
	for (int i=1; i<n; i++) {
		if (arr[i] == arr[i-1]) continue;
	}
	}
*/