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.util.*;
import java.io.*;
import java.math.BigInteger;

 public class Solution {

    static class Pair<A, B> {

        A parent;
        B rank;

        Pair(A parent, B rank) {
            this.rank = rank;
            this.parent = parent;
        }
    }

    static class Node {
        int zero;
        int one;

        Node() {
            zero=one=0;
        }
    }
    static int m=1000000007;
    public static void main(String[] args) throws IOException {
        FastReader s1 = new FastReader();
        StringBuilder sb = new StringBuilder();
        int n=s1.I();
        int ar[] = new int[n];
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i=0;i<n;i++){
            ar[i]=s1.I();
            hm.putIfAbsent(ar[i], 0);
            hm.replace(ar[i],hm.get(ar[i])+1);
        }
        int max=ar[n-1]-1;
        int ans[]= new int[n];
        Arrays.fill(ans,-1);
        TreeSet<Integer> ts = new TreeSet<>();
        int value=1000000;
        for(int i=0;i<=max;i++)
            ts.add(i);
        int till=-1;
        int i=0;
        boolean flag=true;
        while(i<n)
        {
            int temp=ar[i];
            Integer demo = ts.lower(temp);
            if(demo==null)
            {
                boolean ll=false;
                for(int j=ar[i]+1;j<=max;j++)
                {
                    int gg=Arrays.binarySearch(ar,i+1, ar.length-1, j);
                    if(gg<0)
                    {
                        ans[i]=j;
                        ts.remove(j);
                        break;
                    }
                }
            }
            else
            {
                ans[i]=demo;
                ts.remove(demo);
            }
            i++;
        }
        for(i=0;i<n;i++)
        {
            if(ans[i]==-1)
            {
                if(ts.size()==0)
                {
                    ans[i]=ar[n-1]+1;
                }
                else
                {
                    Iterator<Integer> temp = ts.iterator();
                    boolean dd=false;
                    int index=-1;
                    while(temp!=null)
                    {
                        int val=temp.next();
                        int demo=Arrays.binarySearch(ar, i,ar.length-1,val);
                        if(demo<0)
                        {
                            ans[i]=demo;
                            dd=true;
                            index=val;
                        }
                    }
                    ts.remove(index);
                    if(ans[i]==-1)
                        ans[i]=value;
                }
            }
        }
            if(ts.size()>0)
            {
                sb.append("-1\n");
            }
            else
            {
                for(int p:ans)
                {
                    sb.append(p+" ");
                }
                sb.append("\n");
            }
        System.out.println(sb);
    }
    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

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

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

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

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

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

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

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

    static float power(float x, int y) {
        float temp;
        if (y == 0) {
            return 1;
        }
        temp = power(x, y / 2);

        if (y % 2 == 0) {
            return temp * temp;
        } else {
            if (y > 0) {
                return x * temp * temp;
            } else {
                return (temp * temp) / x;
            }
        }
    }
    static long pow(long x, long y) {
        long res = 1;
        x = x % m;
        if (x < 0) {
            x += m;
        }
        while (y > 0) {
            if ((y & 1) == 1) {
                res = (res * x) % m;
                if (res < 0) {
                    res += m;
                }
            }
            y = y >> 1;
            x = (x * x) % m;
            if (x < 0) {
                x = x + m;
            }
        }
        res = res % m;
        if (res < 0) {
            res += m;
        }
        return res;
    }
    static HashSet<Integer> prime;
    static void sieveOfEratosthenes(int n) {
        prime= new HashSet<Integer>();
        boolean Prime[] = new boolean[n + 1];
        for (int i = 2; i < n; i++) {
            Prime[i] = true;
        }
        for (int p = 2; p * p <= n; p++) {
            if (Prime[p] == true) {
                prime.add(p);
                for (int i = p * p; i <= n; i += p) {
                    Prime[i] = false;
                }
            }
        }
    }
}
