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 {

    private static final Parser parser = new Parser();
    private static final Integer MAX_V = 1_000_000;

    public static void main(String[] args) {
        int n = parser.parseInt();

        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = parser.parseInt();
        }

        int[] b = new int[n];
        Arrays.fill(b, MAX_V);

        for(int i = 1; i < n; i++) {
            if(a[i - 1] != a[i]) {
                b[i] = a[i - 1];
            }
        }

        Set<Integer> used = new HashSet<>();
        for(int i = 0; i < n; i++) {
            used.add(b[i]);
        }

        StringBuilder sb = new StringBuilder();
        int curr = 0;
        for(int i = 0; i < n; i++) {
            while (used.contains(curr)) {
                curr += 1;
            }

            if (b[i] != MAX_V) {
                continue;
            }

            b[i] = curr;
            if(b[i] > a[n - 1] - 1){
                b[i] = MAX_V;
            }

            used.add(curr);
        }

        curr = 0;
        used.clear();
        for(int i = 0; i < n; i++) {
            used.add(b[i]);

            while (used.contains(curr)) {
                curr += 1;
            }

            if(b[i] < 0 || curr != a[i]) {
                System.out.println(-1);
                return;
            }
        }

        for(int i = 0; i < n; i++) {
            sb.append(b[i]);
            sb.append(' ');
        }

        System.out.println(sb.toString());
    }
}

class Parser {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final Iterator<String> stringIterator = br.lines().iterator();
    private static final Deque<String> inputs = new ArrayDeque<>();

    void fill() {
        if(inputs.isEmpty()){
            if(!stringIterator.hasNext()) throw new NoSuchElementException();
            inputs.addAll(Arrays.asList(stringIterator.next().split(" ")));
        }
    }

    Integer parseInt() {
        fill();
        if(!inputs.isEmpty()) {
            return Integer.parseInt(inputs.pollFirst());
        }
        throw new NoSuchElementException();
    }

    Long parseLong() {
        fill();
        if(!inputs.isEmpty()) {
            return Long.parseLong(inputs.pollFirst());
        }
        throw new NoSuchElementException();
    }

    Double parseDouble() {
        fill();
        if(!inputs.isEmpty()) {
            return Double.parseDouble(inputs.pollFirst());
        }
        throw new NoSuchElementException();
    }

    String parseString() {
        fill();
        return inputs.removeFirst();
    }
}