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, math
input = sys.stdin.readline

def getInts():
    return [int(s) for s in input().split()]

def getInt():
    return int(input())

def getStrs():
    return [s for s in input().split()]

def getStr():
    return input().strip()

def listStr():
    return list(input().strip())

import collections as col
import math,itertools

"""
We need mex(b1) = a1
If a0 is 0, b0 can be anything greater than 0
If a0 is 1, b0 must be 0
If a0 > 1, impossible

More generally, if a(i-1) > i, impossible (since we would have to have at least 0 to i inclusive in only i spaces)

a0 must not be anything that appears later in the array, so if a0 is 1, then b0 = 0, which means that 0 cannot appear later
There is no point in using an element more than once
So, have a dictionary of elements we need to avoid, with their rightmost index as the value
Maintain a sorted list of numbers we can use
If we exhaust these elements, we can add anything into B that isn't in the banned list, so 10**6-1 works
"""

def solve():
    N = getInt()
    A = getInts()
    B = []
    A_dict = {}
    for j in range(N):
        A_dict[A[j]] = j
    allowed_nums = [j for j in range(N,-1,-1) if j not in A_dict]
    for j in range(N):
        if A[j] > j+1:
            return -1
        B.append(allowed_nums.pop())
        if A_dict[A[j]] == j:
            allowed_nums.append(A[j])
    
    print(*B)
        
    
solve()
    

