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.
"""
MEX(arr) = the smallest non-negative integer which doesn't appear in arr.
Given a SORTED array arr of length n, we want to find another array result s.t.
for i = 0 ... n-1, arr[i] = MEX(result[:i+1]).
Is it possible? If so, give the array.

i   =   0,1,2,3,4,5,6
arr =   1,5,5,4,3,2,1
result= 0,
Not possible.

i   =   0,1,2,3,4,5,6
arr =   1,1,3,4,4,6,7
result= 0,2,1,3,5,4,6

i   =   0,1,2,3,4,5,6
arr =   0,0,0,0,0,0,0
result= any number !=0

i   =   0,1,2,3,4,5,6
arr =   1,2,3,4,5,6,7
result= 0,1,2,3,4,5,6

i   =   0,1,2,3,4,5,6
arr =   1,1,1,1,1,1,1
result= 0,0,0,0,0,0,0

i   =   0,1,2,3,4,5,6
arr =   1,1,1,1,1,1,1
result= 0,0,0,0,0,0,0

i   =   0,1,2,3,4,5,6
arr =   0,2,2,2,3,4,5
result= 1,0,9,9,2,3,4


i   =   0,1,2,3,4,5,6
arr =   0,1,2,3,4,5,6
result= 7,0,1,2,3,4,5

i   =   0,1,2,3,4,5,6
arr =   0,1,3,4,5,6,7
result= 2,0,1,3,4,5,6

i   =   0,1,2,3,4,5,6
arr =   0,1,1,1,1,1,7
result= 2,0,3,4,5,6,1

i   =   0,1,2,3,4,5,6
arr =   0,2,2,3,3,3,7
result= 1,0,4,2,5,6,3

i   =   0,1,2,3,4,5,6
arr =   1,2,2,3,3,3,7
result= 0,1,4,2,5,6,3

Observations:
- Suppose arr[i] = N. Then, if i < N-1, it is not possible.
- It isn't possible if arr isn't sorted. But, that was part of the constraints 
(which I didn't realize until now)
- This means that arr[i] <= i+1 (forall i)
    - Is this sufficient for determining whether it's possible?
    - I think so, since there is so much more freedom for choosing elems of result rather than for arr.
- Will the result always be a permutation of 1...N?
    - No, take any array which all have the same values
- There are 2*3*4*5*6*...*(n+2) possibilities of arr. Actually, less since arr has to be sorted.
- However, n can be up to 10**5, so this probably won't help too much. Maybe for a brute force, though.
- Will the result contain a permutation of [1...max(arr)-1]? 
    - I think so
    - This doesn't quite work, (see an example above)
        - You can just put a garbage value in duplicate elements, so let's not consider them for now.
        - How will this permutation be arranged?
        - Case arr[i] == i.
            - [garbage, 0,1,2,3,...,max(arr)-1]
        - Otherwise:
            - The array must be [0,1,2,...,max(arr)+1] with one element not in there.
                - This must be true because there will be n slots and the maximum is n+1. Furthermore,
                we are not counting duplicates.
            - Then, the answer is [that element, *arr[:-1]]
    - if arr[i] is a new number, then result[i] = the previous unique number.
      if arr[0] == 0, then arr[0] = 1
      if arr[0] == 1, then arr[0] = 0
      Then, you can just go through the other numbers one by one

Solution Ideas:
- Check if forall i, arr[i] <= i+1. If not, then return -1
- This doesn't work:
    - Create a re-indexed array containing only unique values and follow the above procedure to get the solution.
    - Put garbage values everywhere else. The garbage value can be 1000000, since n <= 10**5
- What about keeping track of what items are present in the array. Then, at each element, you can anything 
available except for that element.

"""
import random

def fast(arr):
    result = [-1 for _ in arr]
    used = set()
    seen = set()
    prev = None
    for i, elem in enumerate(arr):
        if elem > i+1:
            return None
        if i == 0:
            prev = elem
            seen.add(elem)
        else:
            if elem not in seen:
                seen.add(elem)
                result[i] = prev
                used.add(prev)
                prev = elem
    ctr = 0
    for i, elem in enumerate(result):
        if elem == -1:
            while ctr in used or ctr == arr[i] or ctr in seen:
                ctr += 1
            result[i] = ctr
            used.add(ctr)
    return result

def main():
    n = int(input())
    arr = [int(x) for x in input().split()]

    #CHANGE
    result = fast(arr)

    if result is None:
        print(-1)
    else:
        print(' '.join(str(x) for x in result))

def MEX(arr):
    ctr = 0
    while ctr in arr:
        ctr += 1
    return ctr

def check(arr, result):
    for i in range(len(arr)):
        print(i, arr[i], result[:i+1], MEX(result[:i+1]))
        if arr[i] != MEX(result[:i+1]):
            return False
    return True

def test():
    # arr = [1,2,2,3,3,3,7]
    # arr = [0,1,3,4,5,6,7]
    # arr = [0,0,0,0,0,0,0]
    #        1,2,3,4,5,6,7
    arr = [0]
    result = fast(arr)
    print(result)
    print(check(arr, result))


def randomTest():
    t = 100
    for i in range(1, t+1):
        n = random.randint(1, 10**5)
        arr = sorted([random.randint(1, n) for _ in range(n)])

        # print(i, arr)
        print(i)

        result = fast(arr)

        if result is None:
            continue

        # if not check(arr, result):
        #     print('Broken!')
        #     print(result)
        #     return


main()
# test()
# randomTest()