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 Main {
    static BufferedReader br;
       //static  long mod  = 1000
    static HashSet<Integer> p  = new HashSet<>();
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 1;
    // tc = cinI();

        while (tc-- > 0) {
                   
                   int ans=-1;
                   int x = 0;
             int  n = cinI();
             ArrayList<Integer> an = new ArrayList<>();
         int[] arr =readArray(n,0,1);
                 
                 for(int j=n-1;j>=0;j--){
                     if(j!=0){
                     if(arr[j]<arr[j-1]){
                      // System.out.println("breakinddsdg");
                         x=1;
                         break;
                     }
                     }
                     if(j+1>=arr[j]){
                         if(arr[j]!=0){
                             an.add(arr[j]-1);
                             continue;
                         }
                         an.add(100001);
                         continue;
                     }
                     else{
                       // System.out.println("breaking");
                         x=1;
                         break;
                     }
                     
                     
                     
                 }
                 if(x==1){
                     System.out.println(-1);
                 }
                 else{
                     StringBuilder ob = new StringBuilder();
                     for(int j=an.size()-1;j>=0;j--){
                         ob.append(an.get(j)+" ");
                         continue;
                     }
                     System.out.println(ob.toString());
                 }
         
        }
    }

























    public static void sieve(){
         int[] pf = new int[100000+1];
        //0 prime //1 not prime
        pf[0]=1;
        pf[1]=1;
        for(int j=2;j<pf.length;j++){

            if(pf[j]==0 && ((long)j*j<pf.length)){
                for(int k=j*j;k<pf.length;k+=j){
                    pf[k]=1;
                }
            }
        }
        for(int j=2;j<pf.length;j++){
          if(pf[j]==0){
              p.add(j);
          }

        }
    }






    public  static  int[] readArray(int n,int x ,int z)throws Exception{
        int[] arr= new int[n];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getI(ar[i-x]);
        }
        return arr;
    }
      public  static  long[] readArray(int n,int x )throws Exception{
        long[] arr= new long[n];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getI(ar[i-x]);
        }
        return arr;
      }

    public static void arrinit(String[] a,long[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Long.parseLong(a[i]);
        }
    }
    public  static HashSet<Integer>[]  Graph(int n,int edge,int directed)throws Exception{
        HashSet<Integer>[] tree=  new HashSet[n];

        for(int j=0;j<edge;j++){

            String[] uv = cinA();
            int u = getI(uv[0]);
            int v = getI(uv[1]);
            if(directed==0){

                tree[v].add(u);
            }
            tree[u].add(v);
        }
        return tree;
    }
    public static void arrinit(String[] a,int[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }
    public static String[] cinA(int x) throws Exception{
        return br.readLine().split("");
    }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static long max(long a, long b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}

class range {
    int l;
    int r;
    int diff;

    public range(int l, int r, int diff) {
        this.l = l;
        this.r = r;
        this.diff = diff;
    }
}

class sortRange implements Comparator<range> {


    @Override
    public int compare(range range, range t1) {
        if (range.diff != t1.diff)
            return t1.diff - range.diff;
        return range.l - t1.l;

    }}
class Diag{

    int c0;
    int c1;
    public Diag(int c0,int c1){
        this.c0=c0;
        this.c1=c1;
    }
}