MEX数组

题解思路

1. 首先使用哈希表统计数组中各个数字出现的次数。
2. 计算整体数组的 MEX 值：
   • 从 0 开始，如果数字 0 出现在数组中，则 MEX 至少为 1；继续判断 1、2、…，直到遇到第一个未出现的数字，此时该数字即为整体数组的 MEX。
3. 对于数组中每个位置，如果删除该位置的元素会改变整体 MEX：
   • 如果当前元素的值小于整体 MEX 且该数字在数组中只出现一次，则删除后该数字从数组中消失，变成缺失的最小非负整数，此时删除后的 MEX 就变为该数字；
   • 否则，删除后数组中仍然包含该数字或该数字本身不影响整体 MEX，删除后的 MEX 与整体 MEX 相同。
4. 最后输出每个位置删除后得到的 MEX 值。

题目内容

小欧有一个长度为$n$的数组$[a_1,a_2,...,a_n]$。现在他想知道，对于$a$中的每个元素，删除该元素后数组的MEX值是多少，请你帮他算算吧。

整数数组的MEX定义为没有出现在数组中的最小非负整数。

输入描述

第一行输入一个整数$n(2 ≤n≤200000)$代表数组中的元素数量。

第二行输入$n$个整数$a_1,a_2,...,a_n$$(0≤a_i≤10^9)$代表数组元素。

输出描述

在一行上输出$n$个整数，其中第$i$个整数表示删除$a_i$后数组的$MEX$值。

样例1

输入

5
0 1 2 3 3

输出

0 1 2 4 4 

说明

删除第一个元素$0$后数组变为$[1，2，3，3]$，其中最小的未出现的非负整数为$0$;

除第二个元素$0$后数组变为$[0，2，3，3]$，其中最小的未出现的非负整数为$1$。