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

	static long m = (long) (1e9 + 7);

	public static void main(String[] args) throws IOException {
		Scanner scn = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = scn.nextInt();
		int a[] = new int[n], b[] = new int[n];
		Arrays.fill(b, -1);
		HashMap<Integer, Integer> hm = new HashMap<>();
		HashMap<Integer, Integer> fm = new HashMap<>();
		for (int i = 0; i < n; i++) {
			a[i] = scn.nextInt();
			hm.put(a[i], i);
			if (!fm.containsKey(a[i]))
				fm.put(a[i], i);
		}
		if (n == 1 || fm.size() == 1) {
			if (a[0] == 0)
				for (int i = 0; i < n; i++)
					sb.append(1 + " ");
			else
				for (int i = 0; i < n; i++)
					sb.append(0 + " ");
			System.out.println(sb);
			return;
		}
		for (int k : hm.keySet())
			if (hm.get(k) + 1 < n)
				b[hm.get(k) + 1] = k;
		int pv = 0, p = pv, j = 0;
		Object[] aa = fm.keySet().toArray();
		for (int l = 1; l < aa.length; l++) {
			while (j <= fm.get(aa[l])) {
				if (b[j] == -1) {
					while (hm.containsKey(pv))
						pv++;
					b[j] = pv;
					if (pv + 1 < (int) aa[l])
						pv++;
				}
				j++;
			}
		}
		for (int v : b)
			if (v == -1)
				sb.append(0);
			else
				sb.append(v + " ");
		System.out.println(sb);
	}

	static class Scanner {

		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}
}