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 class node{
        int k,v;
        node(int k,int v){
            this.k = k;
            this.v = v;
        }
        node(){}
    }


     void solve(Scanner r) throws Exception {
         int n = r.nextInt();
         int arr[] = readIntArray(r,n);

         for (int i = 0; i < n; i++) {
             if (arr[i] > i + 1) {
                 System.out.println(-1);
                 return;
             }
         }

         int cnt = 1;
         int ans[] = new int[n];
         Arrays.fill(ans, -1);
         boolean vis[] = new boolean[(int) 1e6 + 1];
         ArrayList<Integer> av = new ArrayList<Integer>();

         vis[arr[0]] = true;
         for (int i = 1; i < n; i++) {
             if (arr[i] != arr[i - 1]) {
                 ans[i] = arr[i - 1];
                 vis[ans[i]] = true;
                 vis[arr[i]] = true;
             } else {
                 cnt++;
             }
         }

         for (int i = 0; i <= 1000000 && cnt > 0; i++) {
             if (!vis[i]) {
                 av.add(i);
                 cnt--;
             }
         }

         int idx = 0;
         for (int i = 0; i < n; i++) {
             if (ans[i] == -1) {
                 ans[i] = av.get(idx++);
             }
         }

         for (int i = 0; i < n; i++) {
             System.out.print(ans[i] + " ");
         }
    }

    public static int[] readIntArray(Scanner in,int tokens) {
        int[] ret = new int[tokens];
        for (int i = 0; i < tokens; i++) {
            ret[i] = in.nextInt();
        }
        return ret;
    }




    public static void main(String[] args) throws Exception{
//                Scanner in = new Scanner(System.in);
//         Scanner in = new Scanner(new File("input.txt"));
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        new Main().solve(in);

//        int T = in.nextInt();
//        for(int i=1;i<=T;i++){
//            new Main().solve(in);
//        }

    }

}


// class Pair{
//    Integer key, value;
//     Pair(int _key,int _value){
//        key = _key;
//        value = _value;
//    }
//    @Override
//    public int hashCode() {
//        return (key ==null?0: key.hashCode()) ^(value ==null?0: value.hashCode());
//    }
//
//    @Override
//    public boolean equals(Object obj) {
//        if(obj==null) return false;
//        Pair a = (Pair)obj;
//        return this.key.equals(a.key)&&this.value.equals(a.value);
//    }
//}




