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.
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f

def make_next(n, nums):
    imos = [0 for i in range(n)]
    for i, num in enumerate(nums):
        if num > i:
            imos[0] += 1
        else:
            imos[i - num] += 1

        if i + num + 1 < n:
            imos[i+num+1] -= 1
    # print(imos)
    nx = []
    tmp = 0
    for im in imos:
        tmp += im
        nx.append(tmp)

    return nx

def mantan_check(n, nums):
    if sum(nums) == n ** 2:
        return True
    else:
        return False
def knapsack(tree, vx, l):
    dp = [0 for i in range(l + 1)]
    while True:
        dpcp = copy.copy(dp)
        v, w = tree[vx-1]
        # print(v, w)
        for i, d in enumerate(dp):
            if w + i < l + 1:
                if dpcp[w + i] < v + d:
                    dpcp[w + i] = v + d
        dp = copy.copy(dpcp)
        vx //= 2
        dp = dpcp
        # print(dp)
        if vx == 0:
            break

    return max(dp)

def solve():
    n = getN()
    nums = getList()
    ans = [-1 for i in range(n)]
    prev = 0
    used = [0 for i in range(n+10)]
    for i , num in enumerate(nums):
        if num != prev:
            ans[i] = prev
            used[prev] = 1
            prev = num

    used[nums[-1]] = 1
    # print(used)
    used_idx = 0
    for i in range(n):
        if ans[i] == -1:
            while(True):
                if used[used_idx] == 0:
                    ans[i] = used_idx
                    used_idx += 1
                    break
                used_idx += 1

    print(*ans)


def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    solve()

"""
5 10000000000000
4 0 0 0 0
"""