Given an array $a$ of length $n$, find another array, $b$, of length $n$ such that:

  for each $i$ $(1 \le i \le n)$ $MEX(\{b_1$, $b_2$, $\ldots$, $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 \le n \le 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($0 \le a_i \le i$) — the elements of the array $a$. It's guaranteed that $a_i \le a_{i+1}$ for $1\le 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$, $\ldots$, $b_n$ ($0 \le b_i \le 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.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = tuple(map(int, input().split()))
sa = set(a)
san = set()
min_not_in = 0
prev = 0
ans = [0] * n
for i in range(n):
    cur = a[i]
    if cur == prev:
        while min_not_in in sa:
            min_not_in += 1
        ans[i] = min_not_in
        sa.add(min_not_in)
        san.add(min_not_in)
    else:
        ans[i] = prev
        sa.add(prev)
        san.add(prev)
        while prev in san:
            prev += 1
        if cur != prev:
            print(-1)
            break
else:
    print(*ans)


from sys import stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

n, = rl()
a = rl()

a_set = set(a)
free = 0
prev = 0
b = []
for cur in a:
    if cur != prev:
        b.append(prev)
        if free == prev:
            free += 1
        prev = cur
    else:
        while free in a_set:
            free += 1
        b.append(free)
        free += 1
print(*b)


import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
sol=[-1]*n
touse=list(range(n+1))
if a[0]==1:
    sol[0]=0
    touse[0]=-1
for i in range(1,n):
    if a[i]>a[i-1]:
        sol[i]=a[i-1]
        touse[a[i-1]]=-1
j=0
touse[a[-1]]=-1
for i in range(n):
    if sol[i]==-1:
        while touse[j]==-1:
            j+=1
        sol[i]=touse[j]
        j+=1
print(*sol)

from collections import deque
import sys

N = int(input())

A = [int(_) for _ in input().split()]

jokers = deque()

B = [-1] * N
current = 0


for i, el in enumerate(A):
    jokers.append(i)
    if el != current:
        for j in range(el - current):
            if not jokers:
                print(-1)
                return
            p = jokers.pop()
            if A[p] == current + j:
                print(-1)
                return
            else:
                B[p] = current + j
        current = el

while jokers:
    current += 1
    p = jokers.pop()
    B[p] = current

print(' '.join(map(str, B)))