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 bisect
import decimal
from decimal import Decimal
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq 
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate

# sys.setrecursionlimit(200000)
# mod = 10**9+7
# mod = 998244353
decimal.getcontext().prec = 46

def primeFactors(n): 
    prime = set()
    while n % 2 == 0: 
        prime.add(2)
        n = n//2
    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            prime.add(i)
            n = n//i 
    if n > 2: 
        prime.add(n)
    return list(prime)
    
def getFactors(n) : 
    factors = []
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n // i == i) : 
                factors.append(i)
            else : 
                factors.append(i)
                factors.append(n//i)
        i = i + 1
    return factors
    
def SieveOfEratosthenes(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    num = []
    for p in range(2, n+1): 
        if prime[p]: 
            num.append(p)
    return num

def lcm(a,b):
    return (a*b)//math.gcd(a,b)

def sort_dict(key_value):
    return sorted(key_value.items(), key = lambda kv:(kv[1], kv[0]))

def list_input():
    return list(map(int,input().split()))
    
def num_input():
    return map(int,input().split())
    
def string_list():
    return list(input())
    
def decimalToBinary(n):  
    return bin(n).replace("0b", "")  
    
def binaryToDecimal(n): 
    return int(n,2) 
    
def DFS(n,s,adj):              
    visited = [False for i in range(n+1)]  
    stack = [] 
    stack.append(s)  
  
    while (len(stack)):  
        s = stack[-1]  
        stack.pop() 
  
        if (not visited[s]):  
            visited[s] = True 
            
        for node in adj[s]:  
            if (not visited[node]):  
                stack.append(node)  
        
def solve():
    n = int(input())
    arr = list_input()
    if arr[0] != 0 and arr[0] != 1:
        print(-1)
        return
    ans = []
    temp = list(set(arr))
    if len(temp) == 1:
        if temp[0] == 0:
            print('1 '*n)
            return
        elif temp[0] == 1:
            print('0 '*n)
            return
    elif len(temp) == 2:
        if temp[0] == 0 and temp[1] == 1:
            i = 0
            while i < n and arr[i] == 0:
                print(2,end=' ')
                i += 1
            while i < n and arr[i] == 1:
                print(0,end=' ')
                i += 1
            print()
            return
    
    num = [False]*n
    remain = n
    i = 0
    if arr[0] == 1:
        remain -= 1
        prev = 1
        num[0] = True
        ans.append(0)
        i += 1
        while i < n and arr[i] == 1:
            ans.append(-1)
            i += 1
    else:
        prev = 0
        while i < n and arr[i] == 0:
            ans.append(-1)
            i += 1
    while i < n:
        remain -= 1
        num[prev] = True
        ans.append(prev)
        prev = arr[i]
        if i+1 < arr[i]:
            print(-1)
            return
        j = i+1
        while j < n and arr[j] == arr[i]:
            ans.append(-1)
            j += 1
        i = j
    if not(num[1]):
        remain -= 1
        num[1] = True
        ans[0] = 1
    if n > arr[-1]:
        remain -= 1
        num[arr[-1]] = True
    indx = 0
    for i in range(n):
        if ans[i] == -1:
            while indx < n and num[indx]:
                indx += 1
            ans[i] = indx
            if remain > 1:
                num[indx] = True
                remain -= 1
    print(*ans)

#t = int(input())
t = 1
for _ in range(t):
    solve()


    
    
    
    
