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.
################om namh shivay##################37
###############(BHOLE KI FAUJ KREGI MAUJ)############37
from sys import stdin,stdout 
import math,queue,heapq
fastinput=stdin.readline
fastout=stdout.write
t=1 
while t:
    t-=1 
    n=int(fastinput()) 

    #n,m=map(int,fastinput().split())  
    #a=[0]+list(map(int,fastinput().split()))
    b=list(map(int,fastinput().split()))
    #matrix=[list(map(int,fastinput().split())) for _ in range(n)] 
    dubplicate=[]
    ans=[]

    if b[0]==0: 
        ans.append(1) 
    elif b[0]==1:
        ans.append(0) 
    else:
        print(-1) 
        exit()
    flag=False
    for i in range(1,n):
        if b[i]==b[i-1]: 
            x=ans[-1]
            ans.append(x) 
            dubplicate.append(i)
            
        
        elif b[i-1]==0:
            ans.append(0) 
        else:
            if (b[i]-b[i-1]-1)<=len(dubplicate): 
                ans.append(b[i-1]) 
                x=b[i-1]+1 
                
                while  x!=b[i]: 
                    y=dubplicate.pop()
                    ans[y]=x 
                    
                    x+=1 
                
            else:
                flag=True 
                break   
    
    
    if flag:
        print(-1) 
    else:
        print(*ans)
        