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.
/**********************************### With The name of Allah ###***********************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<random>
#include<bitset>
#define ll long long
#define MAX(x,y) x>y?x:y
#define MIN(x,y) x<y?x:y
//int SET(int n,int i) {return (n|(1<<i));}
//int RESET(int n,int i) {return (n&~(1<<i));}
//bool check(int n,int i) {return (n&(1<<i));}
using namespace std;
// To test time Complexity just declare Time veriable in begining of main().
//class Timer {
//    clock_t start;
//    string name;
//public:
//    Timer() {name = "";start = clock();}
//    Timer(string s){name = s;start = clock();}
//    ~Timer() {fprintf(stderr, "%s: %.3gs\n", name.c_str(), 1.0*(clock() - start) / CLOCKS_PER_SEC);}
//};

// This section is for Policy Based Data Structure, more precisely Ordered Set.
// All Functions of set works here, in addition we have order_of_key() and find_by_order() function. find_by_order() returns iterator
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<functional>
using namespace __gnu_pbds;
// All unique value
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set1;
// For storing multiple occurance of same value we need to use pair. In pair first value is our key and second is useless count variable.
// order_of_key(make_pair(key, 0)) returns first occurance of a value, order_of_key(make_pair(key, INT_MAX)) returns last occurance.
typedef tree<pair<int, int>, null_type, less<pair<int,int> >,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// Policy End
// New Modular inverse short.
long long inv(long long a, long long md){ return 1<a ? md - inv(md%a,a)*md/a : 1; }
// This is random generator. Very useful.
mt19937_64 my_rand(std::random_device{}());
ll rnd(ll x){return my_rand()%x;}
// This is Binary Indexted Tree, Again, very useful.	Note: BIT is always indexed from 1 to n, not from 0.
vector<ll> BIT_array;	//Need to resize with required size
// Update value at index i. Here mx should be equal to BIT_array size.
void upd_BIT(int i,ll val, ll mx){for(;i<mx;i+=(i&-i))BIT_array[i]+=val;}
// This returns the sum of values from index 1 to i.
ll sum_BIT(int i){ll res=0;for(;i>0;i-=(i&-i))res+=BIT_array[i];return res;}
// This will return the first position where sum from 0 to pos is not less then s. We can also return the last position where sum less then s. For that return pos insted of pos+1.
ll pos_where_sum_not_less_then_s_BIT(ll s, ll mx){ll pos=0,sum=0;for(ll i=20;i>=0;i--)if(pos+(1<<i)<mx&&sum+BIT_array[pos+(1<<i)]<s)sum+=BIT_array[pos+(1<<i)],pos+=1<<i;return pos+1;}
#define PI atan(1)*4
#define iip pair<int,int>
#define llp pair<ll,ll>
#define MX 100009
int vis[MX];


void input_fun()
{
	 int n;
	 cin>>n;
	 vector<int> arr(n),res(n, -1), vis(n+1,0);
	 for(int &u:arr)cin>>u, vis[u] = 1;
	 if(arr[0]==0)res[0]=1;
	 else res[0] = 0;
	 int pre = arr[0];
	 for(int i=1;i<n;i++){
	 	while(i<n && arr[i]==pre)i++;
		if(i<n)res[i] = arr[i-1], pre = arr[i];
	 }
	 int val = 2;
	 while(vis[val])val++;
	 for(int i=0;i<n;i++){
		 if(res[i]!=-1)continue;
		 res[i] = val++;
		 while(vis[val])val++;
	 }
	 for(int v:res)cout<<v<<" ";
	 cout<<endl;
}

int main()
{
	//freopen("/home/shajal/Desktop/input.txt", "r+", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);

    input_fun();
return 0;
}


