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.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.io.*;

public class Equal {


    static class pair implements Comparable<pair> {
        int x;
        int y;

        public pair(int u, int  v) {
            this.x = u;
            this.y = v;
        }

        @Override
        public int compareTo(pair o) {
            return o.x-x;
        }
    }



    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new FileReader("name.in"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PrintWriter out = new PrintWriter(System.out);
        int n=Integer.parseInt(br.readLine());
        int []a=new int [n];
        int []b=new int[n];
        Arrays.fill(b,-1);
        st=new StringTokenizer(br.readLine());
        int max=-1;
        int firstNotZero=0;
        for (int i = 0; i <n ; i++) {
            a[i]=Integer.parseInt(st.nextToken());
            if(a[i]==0)
                firstNotZero++;
            max=Math.max(max,a[i]);
        }
        boolean vis[]=new boolean[max];
        max++;
        int nextPut=0;
        int lastnotPut=0;
        int sizeAvailable=firstNotZero;
        boolean valid=true;
        for (int i = firstNotZero; i <n ; i++) {
            sizeAvailable++;
            if(i>0&&a[i]==a[i-1]){

                continue;
            }
            if(sizeAvailable<a[i]-nextPut){
                valid=false;
                break;
            }
            b[i]=nextPut;
            if(vis.length>0) {
                vis[nextPut] = true;
                int j=a[i]-1;
                while(j>=0&&!vis[j]){
                    while(b[lastnotPut]!=-1)lastnotPut++;
                    b[lastnotPut++]=j;
                    j--;
                    vis[j]=true;
                }
            }
            sizeAvailable--;
            nextPut=a[i];

        }
        if(valid) {

            for (int i = 0; i < n; i++) {
                if (b[i] == -1)
                    out.print(max);
                else out.print(b[i]);
                if (i < n - 1)
                    out.print(" ");
            }
        }
        else out.print(-1);


        out.flush();
        out.close();

    }

}