Given an array a of length n, find another array, b, of length n such that:

for each i (1≤i≤n) MEX({b1, b2, …, bi})=ai.
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≤105) — the length of the array a.

The second line contains n integers a1, a2, …, an (0≤ai≤i) — the elements of the array a. It’s guaranteed that ai≤ai+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 b1, b2, …, bn (0≤bi≤106)

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.
思路：這個題目卡了好久，一開始思路沒有正確。
我們可以想一下，最終數組中的值，一定是[0,n-1].
我們記錄一下a數組中[0,n-1]沒有出現過的值，保存在數組c中。
如果a[i]==a[i-1]的話，那我們就在c數組中找一個最小的數放置到i這個位置。
如果a[i]≠a[i-1]的話，那我們就將a[i-1]添加到i這個位置。
為什么這樣對呢？
如果a[i]≠a[i-1],對于a[i-1]這個數字，在i-1之前是沒有出現過的，那么在第i個位置出現a[i-1]這個數字就沒有問題。
如果a[i]==a[i-1]的話，在第i個位置放置一個a這個數組中沒有出現過的數字，對目前的結果是沒有影響的。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; int a[maxx]; int b[maxx]; int vis[maxx]; int n;int main() {int t;scanf("%d",&n);memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]=1;int cnt=0;for(int i=n;i>=0;i--) if(!vis[i]) b[++cnt]=i;a[0]=a[1];for(int i=1;i<=n;i++){if(a[i]==a[i-1]) cout<<b[cnt--]<<" ";else cout<<a[i-1]<<" ";}cout<<endl;return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Ehab and Prefix MEXs CodeForces - 1364C（思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。