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.
from sys import stdin, stdout
from sys import maxsize
#input = stdin.readline().strip


def solve():
    pass


test = 1
# test = int(input())
for t in range(0, test):
    # brr = [list(map(int,input().split())) for i in range(rows)]              # 2D array row-wise input
    n = int(input())
    # s = list(input())                                                        # String Input, converted to mutable list.
    # n, x = list(map(int, input().split()))
    a = [int(x) for x in input().split()]
    c = set(a)
    avail = []
    for i in range(n+4):
        if(not i in c):
            avail.append(i)
    b = []
    temp = a[0]
    j = 0
    for i in range(n):
        if(temp != a[i]):
            if(b[i-1]+1 < a[i] and temp < b[i-1]):
                break
            if(temp == b[i-1]+1 and a[i] > temp+1):
                break
            if(a[i] < temp):
                break
            b.append(temp)
            temp = a[i]
        else:
            b.append(avail[j])
            j += 1
    if(len(b) == n):
        for el in b:
            print(el, end=' ')
    else:
        print(-1)


'''
rows, cols = (5, 5)
arr = [[0]*cols for j in range(rows)]                                         # 2D array initialization
b=input().split()                                                             # list created by spliting about spaces
brr = [[int(b[cols*i+j]) for j in range(cols)] for i in range(rows)]          # 2D array Linear Input
rows,cols=len(brr),len(brr[0])                                                # no of rows/cols for 2D array
arr.sort(key = lambda x : x[1])                                               # sort list of tuples by 2nd element, Default priority - 1st Element then 2nd Element
s=set()                                                                       # empty set
a=maxsize                                                                     # initializing infinity
b=-maxsize                                                                    # initializing -infinity
mapped=list(map(function,input))                                              # to apply function to list element-wise
try:                                                                          # Error handling
    #code 1
except:                                                                       # ex. to stop at EOF
    #code 2 , if error occurs
'''
