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 collections import deque
# from itertools import combinations
from heapq import *
# T = int(input().strip())

for t in range(1):
    n = int(input().strip())
    s = list(map(int, input().strip().split()))[:n]
    res = 1
    for  i in range(n-1):
        if (s[i] > i+1) or (s[i+1] < s[i]):
            res = -1
    if res == -1:
        print(-1)
        break

    used = list(set(s)) + [n+1] * n
    rest = list(set(range(2 * n)) - set(s))

    heapify(rest)
    heapify(used)

    startrest = 0
    res = []
    for j in s:
        # print('cur', j, res, used)
        if j <= used[0]:
            res.append(heappop(rest))
        else:
            res.append(heappop(used))
            # curmaxx = max(mex, curmax)

    print(*res)

