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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CEhabAndPrefixMEXs solver = new CEhabAndPrefixMEXs();
        solver.solve(1, in, out);
        out.close();
    }

    static class CEhabAndPrefixMEXs {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] A = new int[n + 1];
            int[] ans = new int[n];
            int[] placedBefore = new int[1000010];
            Arrays.fill(placedBefore, -1);
            int[] placedOnOrAfter = new int[1000010];
            for (int i = 0; i < n; i++) {
                A[i] = in.nextInt() + 1;
                placedOnOrAfter[A[i]] = i + 1;
                if (placedBefore[A[i] - 1] == -1)
                    placedBefore[A[i] - 1] = i + 1;
            }
            int nextPlace = 0;
            boolean invalid = false;
            for (int i = 1000000 - 1; i >= 1; i--) {
                if (placedBefore[i + 1] != -1)
                    if (placedBefore[i] == -1) {
                        placedBefore[i] = placedBefore[i + 1];
                    } else placedBefore[i] = Math.min(placedBefore[i], placedBefore[i + 1]);
            }
            for (int i = 1; i <= 1000000 && nextPlace < n; i++) {
                if (ans[nextPlace] != 0) {
                    nextPlace++;
                    continue;
                }
                if (placedOnOrAfter[i] <= nextPlace && (placedBefore[i] == -1 || placedBefore[i] > nextPlace)) {
                    ans[nextPlace] = i;
                    nextPlace++;
                } else {
                    if (placedBefore[i] != -1 && placedOnOrAfter[i] >= placedBefore[i]) {
                        invalid = true;
                        break;
                    }
                    if (placedBefore[i] != -1 && nextPlace >= placedBefore[i]) {
                        invalid = true;
                        break;
                    }
                    if (placedOnOrAfter[i] >= n) continue;
                    ans[placedOnOrAfter[i]] = i;
                }
            }
            if (nextPlace != n) {
                invalid = true;
            }
            if (invalid) {
                out.println(-1);
            } else {
                for (int i = 0; i < n; i++) {
                    out.print((ans[i] - 1) + " ");
                }
            }

        }

    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

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

    }
}

