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 sys
if sys.subversion[0] == "PyPy":
    import io, atexit
    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))
    
    sys.stdin = io.BytesIO(sys.stdin.read())
    raw_input = lambda: sys.stdin.readline().rstrip()

RS = raw_input
RI = lambda : map(int,RS().split())
RN = lambda : int(RS())
''' ...................................................................... '''
import heapq as hp

def solve():
    n = RN()
    arr = RI()

    for i in xrange(n):
        if arr[i]>i+1:
            print -1
            return

    brr = [-1]*n
    left = []

    for i in xrange(n-1,0,-1):        
        x = arr[i-1]
        y = arr[i]

        for j in xrange(x,y):
            hp.heappush(left,j)

        if left == []:
            brr[i] = 10**6
        else:
            brr[i] = hp.heappop(left)

    for j in xrange(0,arr[0]):
        hp.heappush(left,j)

    if left == []:
        brr[0] = 10**6
    else:
        brr[0] = hp.heappop(left)

    if left != []:
        print -1
        return

    print ' '.join(map(str,brr))

solve()
