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.Scanner;

public class C1364 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] arr = new int[n+2];
		boolean[] exclude = new boolean[100005];
		for (int i = 1; i < n+1; i++)
			arr[i] = in.nextInt();
		for (int i = 1; i < n+2; i++) {
			if (arr[i] != arr[i-1])
				if (arr[i] > 1)
					exclude[arr[i-1]] = true;
		}
		//int count = 1;
		int i = 0;
		String ans = "";
		if (arr[1] == 0) {
			arr[0] = 1;
		} else if (arr[1] == 1) {
			arr[0] = 0;
		} else {
			System.out.println("-1");
			return;
		}
		int j = 1;
		while (i < n) {
			i++;
			if (i + 2 < arr[i]) {
				ans = "-1";
				break;
			}

//			if (j < n) {
//				while (count == arr[j]) {
//					while (count == arr[j]) {
//						j++;
//						if (j >= n)
//							break;
//					}
//					count++;
//					if (j >= n)
//						break;
//				}
//			}

			// System.out.println(arr[i] + " " + count+" "+last);
			if (arr[i] != arr[i-1]) {
				ans += arr[i-1] + " ";
			} else {
//				count++;
//				if (!nums.isEmpty()) {
//					while (count == nums.peek()) {
//						count++;
//						nums.poll();
//						if (nums.isEmpty())
//							break;
//					}
//				}
				do {
					j++;
				} while (exclude[j]);
					
				ans += j + " ";
			}
			// System.out.println(arr[i] + " " + count);
		}
		System.out.println(ans);
	}
}
