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.
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    from itertools import groupby
    B = []
    aa = [[a, list(l)] for a, l in groupby(A)]
    # aa.insert(0, [0 if A[0] == 1 else 1, []])
    p = max(A) + 1
    for i in range(len(aa)-1, 0, -1):
        a, l = aa[i]
        m = len(l)
        n = aa[i-1][0]
        if (p-(a+1)) > m-1:
            return [-1]

        for j in range(a+1, p):
            B.append(j)

        for j in range(m - (p-(a+1))-1):
            B.append(B[-1])

        B.append(n)
        p = a
    a = aa[0][0]
    m = len(aa[0][1])
    if a == 0:
        n = 1
        if (p-(a+1)) > m:
            return [-1]

        if n in B:
            n = 10**6

        for j in range(m):
            B.append(n)
    else:
        n = 0
        if (p-(a+1)) > m-1:
            return [-1]
        for j in range(a+1, p):
            B.append(j)

        for j in range(m - (p-(a+1))-1):
            B.append(B[-1])
        B.append(n)

    return B[::-1]




def main():
    N = read_int()
    A = read_int_n()
    print(*slv(N, A))


if __name__ == '__main__':
    main()
