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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class C {

    public static void main(String[] args) throws IOException {
        new C().run();
    }
    
    private void load_inputs(final BufferedReader br) throws IOException {
        try(
            PrintWriter pw = select_output();
        ) {
                int[] line1 = Arrays.stream(br.readLine().trim().split("\\s+")).mapToInt(v -> Integer.valueOf(v)).toArray();
                int[] line2 = Arrays.stream(br.readLine().trim().split("\\s+")).mapToInt(v -> Integer.valueOf(v)).toArray();
                solve(line1[0], line2, pw);
        }
    }
    
    int len2, n2, trlen;
    long[] tree;
    ArrayList<int[]> queue = new ArrayList<>();
    int[] starts;
    
    private void set(final int i, final long v) {
        int pos = trlen - n2 + i;
        tree[pos] = v;
        while(pos > 0) {
            int pos1 = pos;
            int pos2 = pos + ((pos & 1) == 0 ? -1 : 1);
            pos = (pos - 2 + (pos & 1)) >> 1;
            tree[pos] = tree[pos2] == Long.MIN_VALUE ? tree[pos1] : tree[pos1] + tree[pos2];
        }
    }
    
    private long get(final int l, final int r) {
        int res = 0;
        queue.add(new int[]{0, 0, n2});
        while(queue.size() > 0) {
            int[] item = queue.get(0);
            queue.remove((int)0);
            if(item[1] >= l && item[2] <= r) {
                res += tree[item[0]];
            } else if(item[1] >= r || item[2] < l || item[0] * 2 + 1 >= trlen) {

            } else {
                queue.add(new int[]{item[0] * 2 + 1, item[1], (item[1] + item[2]) / 2});
                queue.add(new int[]{item[0] * 2 + 2, (item[1] + item[2]) / 2, item[2]});
            }
        }
        return res;
    }

    public String toString() {
        return IntStream.range(0, tree.length).mapToObj(i -> (((i + 1) & i) == 0 ? "[" : "") + 
                (tree[i] == Long.MIN_VALUE ? "-" : Long.toString(tree[i])) + 
                (((i + 2) & (i + 1)) == 0 ? "]" : "")).collect(Collectors.joining(", ", "[", "]")) + "\n" +
                Arrays.stream(starts).mapToObj(v -> Integer.toString(v)).collect(Collectors.joining(", ", "[", "]"));
    }
    
    private void init(final long[] a) {
        int n = a.length;
        len2 = (int)Math.ceil(Math.log(n) / Math.log(2));
        n2 = 1 << len2;
        trlen = (n2 << 1) - 1;
        tree = new long[trlen];
        Arrays.fill(tree, Long.MIN_VALUE);
        System.arraycopy(a, 0, tree, trlen - n2, n);
        int start = n2 - 1;
        for(int i = len2 - 1; i >= 0; i--) {
            int stop = ((start + 1) << 1) - 1;
            for(int j = start; j < stop && tree[j] != Long.MIN_VALUE; j += 2) {
                if(tree[j + 1] == Long.MIN_VALUE) {
                    tree[(j - 1) / 2] = tree[j];
                } else {
                    tree[(j - 1) / 2] = tree[j] + tree[j + 1];
                }
            }
            start = ((start + 1) >> 1) - 1;
        }
    }
    
    private int find(final long k, final int i, final int l, final int r) {
//        System.out.println("find: " + k + ", " + i + ", " + l + ", " + r);
        if(l + 1 == r) {
            return l;
        }
        int m = (l + r) >> 1;
        long s = tree[2 * i + 1];
        if(s > k) {
            return find(k, 2 * i + 1, l, m);
        }
        return find(k - s, 2 * i + 2, m, r);
    }
    
    private void solve(final int n, final int[] a, final PrintWriter pw) {
        int[] b = new int[n];
        Arrays.fill(b, -1);
        long[] next_b = new long[n + 1];
        Arrays.fill(next_b, 1);
        for(int i = 1; i < n; i++) {
            next_b[a[i]] = 0;
        }
        b[0] = (a[0] == 0 ? 1 : 0);
        next_b[b[0]] = 0;
        init(next_b);
        int prev_set_i = 0;
        for(int i = 1; i <= n; i++) {
            if(i == n || a[i] != a[i - 1]) {
                if(i < n) {
                    b[i] = a[i - 1];
                    set(b[i], 0);
                }
//                System.out.println("1> b[" + i + "]: " + b[i]);
                for(int j = prev_set_i + 1; j < i; j++) {
                    int k = find(0, 0, 0, n2);
                    b[j] = k;
                    set(k, 0);
                }
//                System.out.println(i - prev_set_i);
                prev_set_i = i;
            }
        }
        pw.println(Arrays.stream(b).anyMatch(v -> v == -1) ? -1 : Arrays.stream(b).mapToObj(v -> Integer.toString(v)).collect(Collectors.joining(" ")));
//        pw.println(Arrays.stream(b).mapToObj(v -> Integer.toString(v)).collect(Collectors.joining(" ")));
    }
    
    String nameIn = getClass().getSimpleName() + ".in";
    String nameOut = null;
    
    private void run() throws IOException {
        File input = null;
        if(nameIn != null && (input = new File(nameIn)).exists()) {
            try(
                FileReader fr = new FileReader(input);
                BufferedReader br = new BufferedReader(fr);
            ) {
                load_inputs(br);
            }
        } else {
            try(
                InputStreamReader fr = new InputStreamReader(System.in);
                BufferedReader br = new BufferedReader(fr);
            ) {
                load_inputs(br);
            }
        }
    }
    
    PrintWriter select_output() throws FileNotFoundException {
        if(nameOut != null) {
            return new PrintWriter(nameOut);
        }
        return new PrintWriter(System.out);
    }
}

