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.io.*;
import java.util.*;
public class Ishu
{
	static boolean srch(int[] a, int l, int r, int data)
	{
	int beg = l;
	int end = r;
	int mid = (beg + end) / 2;
	while(beg <= end)
		{
		mid = (beg + end) / 2;
		if(a[mid] < data)
			beg = mid + 1;
		else if(a[mid] > data)
			end = mid - 1;
		else
			return true;
		}
	return false;
	}
	public static void main(String[] args)
	{
	Scanner scan=new Scanner(System.in);
	int n,i;
	n = scan.nextInt();
	int[] a = new int[n];
	int[] b = new int[n];
	int[] hash = new int[n+1];
	int[] tree = new int[4*n+4];
	for(i=0;i<n;++i)
		a[i] = scan.nextInt();
	if(a[0] == 0)
		{
		b[0] = 1;
		hash[1]++;
		}
	else
		{
		b[0] = 0;
		hash[0]++;
		}
	int j = 0;
	for(i=1;i<n;++i)
		{
		if(a[i] != a[i-1])
			{
			b[i] = a[i-1];
			hash[a[i-1]]++;
			}
		else
			{
			while(true)
				{
				if(j < a[i] && hash[j] == 0)
					break;
				else if(j > a[i] && !srch(a,i+1,n-1,j) && hash[j] == 0)
					break;
				j++;
				}
			hash[j]++;
			b[i] = j;
			}
		}
	for(i=0;i<n;++i)
		System.out.print(b[i]+" ");
	}
}
