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.
#include <bits/stdc++.h>
using namespace std;

#define READ                freopen("in.txt", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)

#define si(a)               scanf("%d", &a)
#define sii(a,b)            scanf("%d %d", &a, &b)
#define siii(a,b,c)         scanf("%d %d %d", &a, &b, &c)

#define sl(a)               scanf("%lld", &a)
#define sll(a,b)            scanf("%lld %lld", &a, &b)
#define slll(a,b,c)         scanf("%lld %lld %lld", &a, &b, &c)

#define CLR(a)              memset(a, 0, sizeof(a))
#define SET(a)              memset(a, -1, sizeof(a))

#define PI                  acos(-1.0)

#define pb                  push_back
#define mp                  make_pair
#define SORT(v)             sort(v.begin(), v.end())
#define REV(v)              reverse(v.begin(), v.end())
#define FOR(i, n)           for(int i=0; i<n; i++)
#define FOR1(i, n)          for(int i=1; i<=n; i++)
#define ROF(i, n)           for(int i=n-1; i>=0; i--)
#define ROF1(i, n)          for(int i=n; i>=1; i--)
#define LOOP(i, x, y)       for(int i=x; i<=y; i++)
#define fastIO()            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


typedef long long              LL;
typedef unsigned long long     ULL;
typedef vector<int>            VI;
typedef pair<int, int>         PII;
typedef pair<string, int>      PSI;
typedef pair<char, int>        PCI;

const int MAX = 1000006;
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;

int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

#define GOOD   1
#define BAD    2
#define FAKA   0
#define WALL   9


int arr[MAX], brr[MAX];
bool taken[MAX];

void solution()
{
    int n; si(n);
    int arr[n];
    FOR(i, n) si(arr[i]);
    SET(brr);

    for(int i=1; i<n; i++){
        if(arr[i-1] < arr[i]){
            brr[i] = arr[i-1];
            taken[brr[i]] = true;
        }
    }

    taken[n] = true;
    int x = 0;
    for(int i=0; i<n; i++){

        if(brr[i] == -1){
            while(taken[x]) x++;

            brr[i] = x;
            taken[x] = true;
        }
    }

    FOR(i, n) cout << brr[i] << " ";
    cout << endl;

}

int main()
{
//    READ;
//    int t; si(t);
//    while(t--)
        solution();

    return 0;
}


			 			  				     	 	  						 	