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;

typedef long long ll;
typedef uint64_t bu;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define rep1(i, a, b) for (int i = a; i < b; i++)
#define rep2(i, a, b) for (int i = a; i <= b; i++)
#define rep3(i, a, b) for (int i = a; i > b; i--)
#define rep4(i, a, b) for (int i = a; i >= b; i--)
#define rep(type, i, a, op, b, change) for (type i = a; i op b; i += change)
#define SQ(a) ll(a) * (a)
#define nl cout << '\n'
#define yes cout << "YES\n"
#define no cout<< "NO\n"s

int Rselect(vector<int>&, int, int, int);
int partition(vector<int>&, int, int);

template<typename T>
ostream& operator<<(ostream& stream, const vector<T>& vec)
{
	for (auto& i : vec)
	{
		stream << i << ' ';
	}
	stream << '\n';
	return stream;
}

template<class T>
istream& operator>>(istream& stream, vector<T>& vec)
{
	for (auto& i : vec)
	{
		stream >> i;
	}
	return stream;
}

void merge_and_count_split(vector<int>& v1, vector<int>& v2, vector<int>& merge_ans, ll& count)
{
	int size1 = v1.size(), size2 = v2.size();
	int i = 0, j = 0;
	for (int k = 0; k < size1 + size2; k++)
	{
		if (j >= size2 || (i < size1 && v1[i] < v2[j]))
		{
			merge_ans[k] = v1[i];
			i++;
		}
		else
		{
			merge_ans[k] = v2[j];
			j++;
			count += size1 - i;
		}
	}
}

void merge_sort(vector<int>& v)
{
	if (v.size() == 1)
	{
		return;
	}
	int s = v.size() / 2;
	vector<int> half1(v.begin(), v.begin() + s);
	vector<int> half2(v.begin() + s, v.end());
	merge_sort(half1);
	merge_sort(half2);
	ll count = 0;
	merge_and_count_split(half1, half2, v, count);
}

ll count_and_sort(vector<int>& v)
{
	int n = v.size();
	if (n == 1)
		return 0;
	int s = n / 2;
	vector<int> half1(v.begin(), v.begin() + s);
	vector<int> half2(v.begin() + s, v.end());
	ll x = count_and_sort(half1);
	ll y = count_and_sort(half2);
	ll count = x + y;
	merge_and_count_split(half1, half2, v, count);
	return count;
}

tuple<ll, ll, ll> euclid(ll a, ll b)
{
	ll d1, x1, y1;
	if (b == 0)
		return { a, 1, 0 };
	else
	{
		tie(d1, x1, y1) = euclid(b, a % b);
	}
	ll d = d1, x = y1, y = x1 - a / b * y1;
	return { d, x, y };
}

int log(ll base, ll n)
{
	ll prod = base;
	int p = 0;
	while (1)
	{
		if (n < prod)
		{
			return p;
		}
		prod *= base;
		p++;
	}
}

ll power(ll m, int n)
{
	ll prod = 1;
	for (int i = 1; i <= n; i++)
	{
		prod *= m;
	}
	return prod;
}

ll phi(ll n) {
	ll result = n;
	for (ll i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			result -= result / i;
		}
	}
	if (n > 1)
		result -= result / n;
	return result;
}

template<class T>
class stack1
{
public:
	void push(T ele)
	{
		if (nums.empty())
		{
			nums.push(ele);
			max_of_nums.push(ele);
		}
		else
		{
			nums.push(ele);
			if (max_of_nums.top() < ele)
			{
				max_of_nums.push(ele);
			}
			else
			{
				max_of_nums.push(max_of_nums.top());
			}
		}
	}
	T top()
	{
		return nums.top();
	}
	void pop()
	{
		nums.pop();
		max_of_nums.pop();
	}
	T stack_max()
	{
		return max_of_nums.top();
	}
	bool empty()
	{
		return (nums.size() == 0);
	}
private:
	stack<T> nums;
	stack<T> max_of_nums;
};

template<class T>
class queue1
{
public:
	void push(T ele)
	{
		st1.push(ele);
		if (st2.empty())
		{
			while (!st1.empty())
			{
				T ele = st1.top();
				st1.pop();
				st2.push(ele);
			}
		}
	}
	void pop()
	{
		st2.pop();
		if (st2.empty())
		{
			while (!st1.empty())
			{
				T ele = st1.top();
				st1.pop();
				st2.push(ele);
			}
		}
	}
	T front()
	{
		return st2.top();
	}
	T queue_max()
	{
		if (!st1.empty() && !st2.empty())
		{
			T ans1 = st1.stack_max();
			T ans2 = st2.stack_max();
			return max(ans1, ans2);
		}
		else if (st1.empty() && !st2.empty())
		{
			return st2.stack_max();
		}
	}
private:
	stack1<T> st1, st2;
};

template<class T>
void counting_sort(T& nums)
{
	int n = nums.size();
	auto [mi, ma] = minmax_element(begin(nums), end(nums));
	int size1 = max(abs(*mi), *ma);
	vector<pair<int, int> > nums1(size1 + 1);
	for (int i = 0; i < n; i++)
	{
		if (nums[i] < 0)
		{
			nums1[abs(nums[i])].first++;
		}
		else
		{
			nums1[nums[i]].second++;
		}
	}
	int j = 0;
	if (*mi < 0)
	{
		for (int i = size1; i > 0; i--)
		{
			while (nums1[i].first > 0)
			{
				nums[j] = -i;
				j++;
				nums1[i].first--;
			}
		}
	}
	for (int i = 0; i <= size1; i++)
	{
		while (nums1[i].second > 0)
		{
			nums[j] = i;
			j++;
			nums1[i].second--;
		}
	}
}

vector<bool> is_prime;
vector<int> primes;
void prime_generator(int n)
{
	is_prime = vector<bool>(n + 1, false);
	vector<bool> a(n + 1, true);
	for (int i = 2; i * i <= n; i++)
	{
		if (a[i])
		{
			for (int j = i * i; j <= n; j += i)
			{
				a[j] = false;
			}
		}
	}
	for (int i = 2; i <= n; i++)
	{
		if (a[i])
		{
			is_prime[i] = true;
			primes.pub(a[i]);
		}
	}
}

vector<int> spf;
void sieve(int n)
{
	spf = vi(n + 1);
	spf[1] = 1;
	for (int i = 2; i <= n; i++)
		spf[i] = i;
	for (int i = 4; i <= n; i += 2)
		spf[i] = 2;

	for (int i = 3; i * i <= n; i++)
	{
		if (spf[i] == i)
		{
			for (int j = i * i; j <= n; j += i)
				if (spf[j] == j)
					spf[j] = i;
		}
	}
}

vector<int> getFactorization(int x)
{
	vector<int> ret;
	while (x != 1)
	{
		ret.push_back(spf[x]);
		x = x / spf[x];
	}
	return ret;
}

void radix_sort(vector<int>& arr)
{
	int d = 0;
	for (const auto& i : arr)
	{
		d = max(d, log(10, i) + 1);
	}
	int n = arr.size();
	vector<queue<int> > digits(10);
	ll prod = 10;
	vector<int> tmp = arr;
	while (d--)
	{
		for (int i = 0; i < n; i++)
		{
			digits[tmp[i] % 10].push(arr[i]);
		}
		int index = 0;
		for (int i = 0; i < 10; i++)
		{
			while (!digits[i].empty())
			{
				arr[index] = digits[i].front();
				tmp[index] = arr[index] / prod;
				digits[i].pop();
				index++;
			}
		}
		prod *= 10;
	}
}

void solve();

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

void solve()
{
	int n;
	cin >> n;
	vi a(n);
	cin >> a;
	//int var = 0;
	vi cnt(n, 0);
	vi b(n, 1000000);
	if (a[0] == 1)
		b[0] = 0;
	int i = 0, j = 1;
	if (b[0] == 0)
		i = 1;
	while (i < n && j < n)
	{
		if (a[j] != a[j - 1])
		{
			int diff = a[j] - a[j - 1];
			//var = j - i + 1
			if (j - i + 1 < diff)
			{
				cout << -1 << '\n';
				return;
			}
			else
			{
				int value = a[j - 1] + 1;
				while (value < a[j])
				{
					b[i] = value;
					value++;
					do
					{
						i++;
					} while (b[i] != 1000000);
				}
				b[j] = a[j - 1];
			}
		}
		j++;
	}
	cout << b;
}

int Rselect(vector<int>& v, int i, int l, int r)
{
	if (l == r)
		return v[l];
	int pivot = partition(v, l, r);
	if (pivot == i)
		return v[pivot - 1];
	else if (pivot < i)
	{
		return Rselect(v, i, pivot, r);
	}
	else
	{
		return Rselect(v, i, l, pivot - 2);
	}
}

int partition(vector<int>& v, int l, int r)
{
	int pivot_index = rand() % (r - l + 1) + l;
	swap(v[pivot_index], v[l]);
	int i = l + 1, j = l + 1;
	while (j <= r)
	{
		if (v[j] < v[l])
		{
			swap(v[j], v[i]);
			i++;
		}
		j++;
	}
	swap(v[l], v[i - 1]);
	return i;
}
