题解

题面描述

给定一个整数 $n$ 和一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$。定义任意区间 $[l,r]$ 的数字凸包区间为

对于每个前缀 $[1,i]$（$i=1,2,\dots,n$），求该前缀构成的数字凸包区间中不属于该区间的最小非负整数。

例如：

• 当 $i=1$ 时，区间为 $[\min\{a_1\},\max\{a_1\}]=[a_1,a_1]$，如果 $a_1\neq 0$ 则 $0$ 不在该区间，答案为 $0$；

题目内容

米小游有$n$个整数{$a_1,a_2,...,a_n$}，他定义区间$[l,r]$的“数字凸包区间”为 [$min${$a_l,...,a_r$},$max${$a_l,...,a_r$}]。

现在，对于每一个$i= 1,2,...,n$，直接输出不属于$[1,i]$这个区间的“数字凸包区间”的最小非负整数。

输入描述

第一行输入两个整数$n(1≦n≦2×10^5)$代表整数数量询问次数。

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

输出描述

在一行上输出$n$个整数，代表对于每一个$i$的答案。

样例1

输入

5
1 0 4 5 1

输出

0 2 5 6 6

说明

对于第一次询问，“数字凸包区间”为$[1,1]$，不属于这个“数字凸包区间”的最小非负整数为$0$。

对于第二次询问，“数字凸包区间”为$[0,1]$，不属于这个“数字凸包区间”的最小非负整数为$2$。