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 f(a,b) for( int i1=a;i1<=b;i1++)
#define f1(a,b) for( int i=a;i<=b;i++)
#define f2(a,b,c) for(unsigned int i2=a;i2<=b;i2+=c)
typedef long long int  ll;
const int max1=105;
int abs(int k){
	return((k>0)?k:-k);
}
		
void solve(){
int n;
cin>>n;

ll a[n];
int c=0;

int cnt[n]={0};
f(0,n-1){cin>>a[i1];}
f(0,n-1){
	cnt[a[i1]]=1;

}
int r[n-1]={0};
f(0,n-1){
	if(a[i1]>i1+1){
		cout<<-1;
		break;
	}

	if(a[i1]==c){
		int k=a[i1]+1;
		while(cnt[k]!=0){++k;}
		r[i1]=k;
		
		}
		else{
			r[i1]=c;
			++c;
		}

}
f(0,n-1){cout<<r[i1]<<" ";}


}


int main(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
	#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	solve();
   /*
   int t;
   cin>>t;
   while(t--){
   
   	cout<<"\n";

   }*/
  
return 0;
}