#D6248. Ehab and Prefix MEXs
Ehab and Prefix MEXs
Ehab and Prefix MEXs
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.
inputFormat
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.
outputFormat
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.
样例
3
1 2 3
0 1 2