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.
//package test.codeforce.c649;

import java.util.*;

public class C
{

	public static void main(String[] args)
	{
		Scanner input = new Scanner(System.in);

		StringBuffer stringBuffer = new StringBuffer();

		int n = input.nextInt();
		int ans = 0;
		//������������
		int[] an = new int[n];
		int[] bn = new int[n];
		Arrays.fill(bn, -1);
		int k = 0;
		Set<Integer> map = new HashSet<>();
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++)
		{
			an[i] = input.nextInt();
			max = Math.max(max, an[i]);
		}
		if (an[0] != 1 && an[0] != 0)
		{
			stringBuffer.append(-1 + "\n");
		} else
		{
			if (an[0] == 1)
			{
				bn[k] = 0;
				map.add(0);
				k++;
			} else
			{
				bn[k] = 1;
				map.add(1);
				k++;
			}
			for (int i = 1; i < n; i++)
			{
				if (an[i] == an[i - 1])
				{
					continue;
				} else
				{
					int start = an[i - 1];
					int end = an[i];
					bn[i] = start;
					start++;
					while (k <= i - 1 && start < end)
					{
						if (!map.contains(start) && bn[k] == -1)
						{

							bn[k] = start;
							start++;
							k++;

						}
						if (bn[k] != -1)
						{
							k++;
						} else
						{
							start++;
						}
					}
					if (start < end - 1)
					{
						System.out.println(-1);
						return;
					}
				}

			}

		}
		for (; k < n; k++)
		{
			if (bn[k] == -1)
			{
				bn[k] = max + 1;
			}

		}
		for (int i = 0; i < n; i++)
		{
			if (i == n - 1)
			{
				stringBuffer.append(bn[i] + "\n");
			} else
			{
				stringBuffer.append(bn[i] + " ");
			}

		}

		System.out.println(stringBuffer.toString());
	}
}
