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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/**
 * @author Lin
 * @version 1.0
 * @date 2020/11/28 21:00
 */
public class EhabAndPrefixMEXs
{
	/**
	 * 7
	 * 0 0 2 2 5 5 6
	 */
	public static void main(String[] args) throws IOException
	{
		StringBuffer stringBuffer = new StringBuffer();
		int n = Reader.nextInt();
		int[] an = new int[n + 1];
		int[] bn = new int[n + 1];
		for (int i = 0; i < n; i++)
		{
			an[i + 1] = Reader.nextInt();
		}
		bn[n] = an[n];
		Queue<Integer> queue = new LinkedList<>();
		int r = an[n];
		for (int i = n; i >= 1; i--)
		{
			while (i > 0 && an[i] == an[i - 1])
			{
				while (!queue.isEmpty() && r - 1 == queue.peek())
				{
					r--;
					queue.poll();
				}
				if (r - 1 > an[i - 1])
				{
					bn[i - 1] = --r;
					;
				} else
				{
					bn[i - 1] = an[n] + 1;
				}

				i--;
			}
			while (!queue.isEmpty() && r - 1 == queue.peek())
			{
				r--;
				queue.poll();
			}
			if (i > 0 && an[i] != an[i - 1])
			{
				queue.add(an[i - 1]);
				bn[i - 1] = an[i - 1];
				if (r + 1 - (i - an[i - 1] - 1) > an[i] + 1)
				{
					System.out.println(-1);
					return;
				}
			}
		}
		stringBuffer.append(bn[0]);
		for (int i = 1; i < n; i++)
		{
			stringBuffer.append(" " + bn[i]);
		}
		System.out.println(stringBuffer.toString());
	}
	static class Reader
	{
		static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		static StringTokenizer tokenizer = new StringTokenizer("");
		static String nextLine() throws IOException
		{// 读取下一行字符串
			return reader.readLine();
		}
		static String next() throws IOException
		{// 读取下一个字符串
			while (!tokenizer.hasMoreTokens())
			{
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		static int nextInt() throws IOException
		{// 读取下一个int型数值
			return Integer.parseInt(next());
		}
		static long nextLong() throws IOException
		{// 读取下一个int型数值
			return Long.parseLong(next());
		}
		static double nextDouble() throws IOException
		{// 读取下一个double型数值
			return Double.parseDouble(next());
		}
	}
}
