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 os

import sys

debug = True

if debug and os.path.exists("input.in"):
    input = open("input.in", "r").readline
else:
    debug = False
    input = sys.stdin.readline


def inp():
    return (int(input()))


def inlt():
    return (list(map(int, input().split())))


def insr():
    s = input()
    return s[:len(s) - 1]  # Remove line char from end


def invr():
    return (map(int, input().split()))


test_count = 1
if debug:
    test_count = int(input())

for t in range(test_count):
    if debug:
        print("Test Case #", t + 1)
    # Start code here
    n = inp()
    a = inlt()
    curr_index = 0
    last_value = -1
    ok = True
    max_value = max(a)
    ans = [max_value + 1 for x in range(n)]

    for i in range(n):
        curr = a[i]
        if curr == 0:
            continue
        if curr > i + 1:
            ok = False
            break
        else:
            value_to_fill_start = curr - 1
            value_to_fill_end = max(last_value, 0)
            last_filled = -1
            for j in range(value_to_fill_start, value_to_fill_end - 1, -1):
                while curr_index <= i:
                    if j <= a[curr_index] and curr_index != i:
                        curr_index += 1
                    else:
                        ans[curr_index] = j
                        curr_index += 1
                        last_filled = j
                        break
                if curr_index > i:
                    break
            if last_filled != value_to_fill_end:
                ok = False
                break

        last_value = curr
        if not ok:
            break

    if ok:
        print(" ".join(map(str, ans)))
    else:
        print(-1)
