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 solution {
    List<Integer> primeList = new ArrayList<Integer>();
    int MAX_N = Integer.MAX_VALUE;
    boolean[] isPrime = new boolean[MAX_N];
    public static void main(String[] args) throws  Exception{
        FastReader sc;
        PrintWriter out = new PrintWriter(System.out);;
        if(System.getProperty("ONLINE_JUDGE")==null)
        {
            sc = new FastReader("/Users/jenardn/IdeaProjects/codeforces/input");
        }
        else
        {
            sc = new FastReader();
        }
        out = new PrintWriter(System.out);
        Task solver = new Task();
        long t = 1;
//        t = sc.nextInt();
        for(long i = 1; i <= t; i++){
            solver.solve(i, sc, out);out.println();
        }
        out.close();
    }

    static class Task {
        public void solve(long testNumber, FastReader sc, PrintWriter out) {
            int n = sc.nextInt();
            int [] arr = new int[n];
            int [] map = new int[1000001];
            Arrays.fill(map,-1);
            for(int i=0;i<n;i++)
            {
                arr[i] = sc.nextInt();
                map[arr[i]]=i;
            }
            List<Integer> nextAvailable = new ArrayList<Integer>();
            int[] ans = new int[n];
            for(int i=0;i<=100000;i++)
            {
                if(map[i]==-1)
                {
                    nextAvailable.add(i);
                }
            }
            int ptr=0,readyNum=-1;
            for(int i=0;i<n;i++)
            {
                if(readyNum!=-1)
                {
                    ans[i]=readyNum;
                    readyNum=-1;
                }
                else
                {
                    ans[i]= nextAvailable.get(ptr);ptr++;
                }
                if(map[arr[i]]<=i)
                {
                    readyNum = arr[i];
                }
            }
            for(int i=0;i<n;i++)
            {
                out.print(ans[i]+" ");
            }
        }
    }

    long modulo_multiplication(long a, long b, long mod)
    {
        long res = 0;
        a %= mod;
        while (b>0)
        {
            if ((b & 1)>0)
                res = (res + a) % mod;
            a = (2 * a) % mod;
            b >>= 1;
        }
        return res;
    }
    void sieve()
    {
        Arrays.fill(isPrime,true);
        for (int i = 2; i <= MAX_N; i++)
        {
            if (isPrime[i])
            {
                for (int j = 2 * i; j <= MAX_N; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }
    }

    void setPrimeList()
    {
        for (int  i = 2; i < MAX_N; i++)
        {
            if (isPrime[i])
            {
                primeList.add(i);
            }
        }
    }

    long gcd(long a, long b) { if (a == 0) return b; return gcd(b % a, a);}

    long mod_power(long x, long y, long p)
    {
        long res = 1;
        x = x % p;
        if (x == 0) return 0;
        while (y > 0)
        {
            if ((y & 1)>0)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

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

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}