#649 (Div. 2)C. 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({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

inputCopy 3 1 2 3 outputCopy 0 1 2 inputCopy 4 0 0 0 2 outputCopy 1 3 4 0 inputCopy 3 1 1 3 outputCopy 0 2 1

Note

In the second test case, other answers like [1,1,1,0], for example, are valid.

题目分析

我们可以将a[]中没有的数放入一个小根堆中，每次输出堆顶元素，然后移除堆顶元素。如果a[]中某个元素已经没有了，那么就将该元素再放入堆中。

代码如下

#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <stack> #include <map> #include <unordered_map> #include <queue> #include <vector> #include <set> #include <algorithm> #include <iomanip> #define LL long long using namespace std; const int N=1e5+5; int a[N]; bool st[N]; int main() { int n; cin>>n; priority_queue<int,vector<int>,greater<int> > heap; for(int i=1;i<=n;i++) { cin>>a[i]; st[a[i]]=true; //记录a[]中元素 } for(int i=0;i<2*n;i++) { if(!st[i]) heap.push(i); //如果a[]中没有某个元素，就将其放入堆中 } for(int i=1;i<=n;i++) { cout<<heap.top()<<' '; //每次输出堆顶元素 heap.pop(); if(a[i+1]!=a[i]) heap.push(a[i]); //当a[]中没有相同的元素时，便可将a[i]放入堆中（a[]中的元素是单调递增的） } return 0; }