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.*;
public class A{
    static PrintWriter out;
    static InputReader in;
    public static void main(String args[]){
        out = new PrintWriter(System.out);
        in = new InputReader();
        new A();
        out.flush(); out.close();
    }   
    A(){
        solve();
    }
    void solve(){
        int n = in.nextInt();
        int a[] = new int[n];
        TreeSet<Integer> ts = new TreeSet<>();
        for(int i = 0; i <= n; i++)ts.add(i);
        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
            ts.remove(a[i]);
        }
        ArrayList<Integer> ans = new ArrayList<>();
        int b = -1;
        for(int i = 0; i < n; i++){
            if(a[i] != b && b != -1)ts.add(b);
            // while(!ts.isEmpty() && ts.first() < a[i] - 1){
            //     ts.pollFirst();
            // }
            // if(ts.isEmpty()){
            //     out.println(-1);
            //     return;
            // }
            ans.add(ts.pollFirst());
            b = a[i];
        }
        // System.out.println(ans);
        boolean inc[] = new boolean[n + 10];
        int mex = 0;
        for(int i = 0; i < n; i++){
            int v = ans.get(i);
            inc[v] = true;
            while(inc[mex])++mex;
            if(mex != a[i]){
                out.println(-1);
                return;
            }
        }
        for(int v : ans)out.print(v + " ");
    }
    public static class InputReader{
        BufferedReader br;
        StringTokenizer st;
        InputReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public long nextLong(){
            return Long.parseLong(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
        public String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){}
            }
            return st.nextToken();
        }
    }
}
        